ZOJ 3802 Easy 2048 Again 状态DP

zoj 上次的月赛题，相当牛的题目啊，根本想不到是状态压缩好吧

有个预先要知道的，即500个16相加那也是不会超过8192，即，合并最多合并到4096，只有2的12次方

所以用状态压缩表示前面有的序列组合，找到了符合的，就往上累加合并生成新状态，否则就添加到前面的状态的后面构成新状态，因为每一个的状态都由前一个所得，用滚动数组即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[2][4097*2];
int A[510];
int n;
int main()
{
    int ti;
    scanf("%d",&ti);
    while (ti--)
    {
        memset(dp,-1,sizeof dp);
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&A[i]);
        }
        int pos=1;
        int ans=0;
        dp[0][0]=0;
        for (int i=1; i<=n; i++)
        {
            for (int j=0; j<4096*2; j++)
            {
                if (dp[pos^1][j]==-1) continue;
                dp[pos][j]=max(dp[pos][j],dp[pos^1][j]);
                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;
        }
        printf("%d
",ans);
    }
}