链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5334

题意：一个长度为500的数列，每个数可能是2，4，8，16，从第一个开始取，每个数可以选择取或者不取，如果取了x，这个数和之前的数如果相同，那么两个数会合并成为2*x并且收起来，如果不同就把这个数收起来。

思路：比如像要凑成2048，必须拥有一个1024,512,256,128,64,32,16,8,4,2中某段从1024开始的连续递减序列，然后再取得一个和末尾数相同的数才能连续合并成为2048。

所以状态压缩只需要记录递减序列的状态存在情况进行压缩即可，DP[i][j]记录的是第i位置所取到的j情况递减序列，第1位是2，第2位是4，第3位8..（500个16的极限情况也只有8000，所以最多只需要12位，也就是最高位4096来记录，所以只有4095种情况，因为不存在1和0的情况）.用一个二进制数来表示这些位是否有取到。问题关键在于如果将第i位合并进去，必须保证该状态下第1~i-1位都是0，否则就不是连续递减序列。

P.S.比赛时候想这道题想的复杂了，比如2 2 2 这种情况我认为还要考虑是合并成2 4，还是合并成4 2两种状况，实际上不需要，因为没取一个数就进行自动合并，而不是要我决定是否合并。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int dp[505][4100];
int a[505],Pow[15];
map < int,int > M;
void init()
{
    memset(dp,-1,sizeof(dp));
    M[2]=1;
    int pos=2;
    for(int i=2; i<=12; i++)
    {
        pos*=2;
        M[pos]=i;
    }
    return ;
}
int main()
{
    int T,tot;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&tot);
        for(int i=1; i<=tot; i++)
            scanf("%d",&a[i]);
        dp[1][a[1]>>1]=a[1];
        for(int i=2; i<=tot; i++)
        {
            int dn=(a[i]>>1)-1;
            dp[i-1][0]=0;
            for(int j=0; j<4096; j++)
            {
                if(dp[i-1][j]>dp[i][j])
                    dp[i][j]=dp[i-1][j];
                if((j&dn)==0&&dp[i-1][j]!=-1)
                {
                    int ans=0;
                    int k=a[i]>>1;
                    while(1)
                    {
                        if((k&j)==0)
                            break;
                        k*=2;
                        ans+=k*2;
                    }
                    int next=j-(ans>>2)+k;
                    dp[i][next]=max(dp[i-1][j]+ans+a[i],dp[i][next]);
                }
                else if((j&dn)!=0&&dp[i-1][j]!=-1)
                {
                    dp[i][dn+1]=max(dp[i][dn+1],dp[i-1][j]+a[i]);
                }
            }
        }
        int ans=0;
        for(int i=0; i<4096; i++)
        {
            ans=max(ans,dp[tot][i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

ZOJ 3802 Easy 2048 Again 状压DP