状压DP系列

几点注意：

1.数组下标从1开始比较方便

zoj Easy 2048 Again
保存状态的时候是保存下降子序列的情况，没有下降子序列就只保存当前最后一个数，不是的数则直接不管，因为后面用不到。
开二维数组超时，要用滚动数组优化。

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

int dp[2][4097*2];    //滚动数组
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个数前的状态
                if(dp[pos^1][j]==-1) continue;    //如果为-1表示不能达到这种状态
                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的比例,按一个分数表示.

#include<iostream>
#include <cstdio>  
#include <cstring>  
using namespace std;
const int N = 13;  
int dp[1<<13][510];   ///dp[i][j]表示取i的二进制位值兴趣值为j时的个数  
int fab[N];   ///所有可能情况  
int a[N][N];  
  
int gcd(int a,int b)  //最大公约数 
{  
    if(b==0)  
        return a;  
    else  
        return gcd(b,a%b);  
}  
int main()  
{  
    fab[0]=1;               //每种题数的所有可能情况 
    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++)  //用二进制的位数表示对应的题数，1取0不取然后将二进制转换成十进制，降低循环次数 
        {
            int tmp=0;          //已经取的题数 
            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]);  //题目要求最简分数 
            printf("%d/%d\n",fab[n]/tm, dp[(1<<n)-1][m]/tm);  
        }  
    }  
}