幾點注意：

1.數(shù)組下標從1開始比較方便

zoj Easy 2048 Again
保存狀態(tài)的時候是保存下降子序列的情況镶柱，沒有下降子序列就只保存當前最后一個數(shù)极谊，不是的數(shù)則直接不管忽冻，因為后面用不到馅而。
開二維數(shù)組超時溉贿，要用滾動數(shù)組優(yōu)化仑嗅。

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;

int dp[2][4097*2];    //滾動數(shù)組
int a[510];
int n;
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(dp,-1,sizeof(dp));
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int pos=1,ans=0;
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<4096*2;j++){   //j為取第i個數(shù)前的狀態(tài)
                if(dp[pos^1][j]==-1) continue;    //如果為-1表示不能達到這種狀態(tài)
                dp[pos][j]=max(dp[pos][j],dp[pos^1][j]);  //第i位不取
                ans=max(ans,dp[pos][j]);
                int t=j;
                int q=a[i]-1;
                int sum=a[i];
                if((t&q)==0){
                    int k=a[i];
                    while((t&k)){
                        sum+=k<<1;
                        k<<=1;
                    }
                    t&=~(k-1);
                    t|=k;
                }
                else 
                    t=a[i];
                dp[pos][t]=max(dp[pos][t],dp[pos^1][j]+sum);
                ans=max(ans,dp[pos][t]);
            }
            pos^=1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

zoj 3777 Problem Arrangement
題意：給出n道題目以及每一道題目不同時間做的興趣值畦浓，讓你求出所有做題順序中興趣值不小于m的比例,按一個分數(shù)表示.

#include<iostream>
#include <cstdio>  
#include <cstring>  
using namespace std;
const int N = 13;  
int dp[1<<13][510];   ///dp[i][j]表示取i的二進制位值興趣值為j時的個數(shù)  
int fab[N];   ///所有可能情況  
int a[N][N];  
  
int gcd(int a,int b)  //最大公約數(shù) 
{  
    if(b==0)  
        return a;  
    else  
        return gcd(b,a%b);  
}  
int main()  
{  
    fab[0]=1;               //每種題數(shù)的所有可能情況 
    for(int i=1;i<13;i++)
        fab[i]=fab[i-1]*i;
    int t,m,n;  
    cin>>t;   
    while(t--)  
    {  
        cin>>n>>m;
        for(int i=1;i<=n;i++)   //下標從1開始可以方便操作 
        {
            for(int j=1;j<=n;j++)
                cin>>a[i][j]; 
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=0;i<=(1<<n);i++)  //用二進制的位數(shù)表示對應的題數(shù)痹束，1取0不取然后將二進制轉(zhuǎn)換成十進制，降低循環(huán)次數(shù) 
        {
            int tmp=0;          //已經(jīng)取的題數(shù) 
            for(int j=1;j<=n;j++){  
                if(i&(1<<(j-1))) 
                    tmp++;
            } 
            for(int j=1;j<=n;j++)
            {   
                if(i&(1<<(j-1))) //取過的不操作 
                    continue; 
                for(int k=0;k<=m;k++)   //k為當前的所有可能取值 
                    if(k+a[tmp+1][j]>=m)    //比m大的值當成m處理 
                        dp[i+(1<<(j-1))][m]+=dp[i][k]; 
                    else
                        dp[i+(1<<(j-1))][k+a[tmp+1][j]]+=dp[i][k];
            } 
        } 
        if(dp[(1<<n)-1][m] == 0)  //不存在 
            printf("No solution\n");  
        else  
        {  
            int tm = gcd(fab[n],dp[(1<<n)-1][m]);  //題目要求最簡分數(shù) 
            printf("%d/%d\n",fab[n]/tm, dp[(1<<n)-1][m]/tm);  
        }  
    }  
}