zoj月赛的题目，非常不错的一个状压dp。。

题目大意是一个一维的2048游戏

只要有相邻的相同就会合并，合并之后会有奖励分数，总共n个，每个都可以取或者不取

问最终得到的最大值

数据范围n<=500 , a[i]={2，4，8，16}；

分析：

首先明确一下自动合并的意思，比如原有 8，4，2，进入一个2 就会变成16

所以我们需要记录前面的所有数字。。计算了一下发现最大情况，500个16会合成4096 =2^12

显然全部记录是不可能的。那么怎么处理呢

我们发现，只有递减的序列才有可能向前合并。。所以我们只需要记录某个状态末尾的递减序列即可

最大数只有2^12，所以递减序列个数只有2^13-1种，可以记录了。。

之后就是状态转移的问题了。

不取当前数状态不变

取当前数分三种情况

1.前面有比当前数更小的，则如果取这个数，递减序列将只有这一个数

2.前面的末尾恰好跟当前数相等，那么向上合并直至不能合并为止 

3.前面的末尾比当前数大，那么直接将当前数插入状态中

具体实现看代码，用了一点位运算挺有意思的

#include 
     
      #include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define MAXN 10000int dp[2][8200];int a[505];int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); #endif int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",a+i); } memset(dp,-1,sizeof(dp)); dp[1][0]=0; dp[1][a[1]]=a[1]; for(int i=2;i<=n;i++) { for(int j=0;j<=8191;j++) { if(dp[(i-1)%2][j]==-1) { continue; } dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j]); //不取 if(j&(a[i]-1)) { dp[i%2][a[i]]=max(dp[i%2][a[i]],dp[(i-1)%2][j]+a[i]); //情况1 continue; } int state,score; if(j&a[i]) { int tmp=j/a[i],k=0; score=a[i]; while(tmp%2) { k++; tmp/=2; score+=a[i]<