先mark一下，感觉自己好难理解。。。。正在理解中，，，，
**************************************************
几乎折腾了一下午。。。表示很痛苦。不过终于有了点理解，虽然代码可能基本就是和别人一样的了。。。。。
不过也算是学习的过程吧。。。。
然后我多打几遍在理解一下再来更新。。。。。。
*************************************************
看了好多题解，终于有了点眉目。
DP[I][J]表示前i个数中，j状态下可以得到的最大值。因为可能会爆内存，所以用了滚动数组。然后j状态存储的实际上是当前状态递减的序列，用二进制表示。因为如果当前数组末尾没有递减的数列，那么就算合并也不能再继续合并了，所以这样处理。
原先一直不理解为什么每次DP的时候要枚举到最大值，或者说不知道怎么枚举上一次得到的（剩下的）容量。然后这次好像又懂了一点点。。。如果原先出现过这样的情况，那么等到下次你枚举到这个情况的时候就会再次碰到他，这也是为什么要枚举到最大值。
DP方程用了两次，第一次是不取当前的a[i]，取了当前状态的最大值。然后假设取了当前的a[i]，然后看看可以合并多少次，算出得到的奖励和合并后的状态。
第二次表示合并后的那种状态是由原先某种路径得来的比较好，还是由这一次经过以上方式合并得来的比较好。
/*
3
4
2 8 4 8
5
2 2 4 8 16
8
8 4 4 2 8 4 2 2
*/
#include <stdio.h>
#include <string.h>
#define maxn 5000
int n,dp[2][maxn],a[maxn],sum,score[maxn];
int max(int x,int y)
{
if(x>y) return x;
else return y;
}
void solve()
{
int i,j,k;
int pre=0,now=1;
dp[pre][0]=0;
for(i=0;i<n;i++)
{
for(j=0;j<=4096;j++)
{
if(dp[pre][j]!=-1)
{
dp[now][j]=max(dp[now][j],dp[pre][j]);
int t=j;
k=a[i]-1;
int tmp=(1<<k)-1;
int get=score[a[i]];
if((tmp&t)==0)
{
while(t&(1<<k))
{
get+=score[k+2];
k++;
}
tmp=(1<<k)-1;
t&=~tmp;///把比k低的位数全变成0
t|=1<<k;
}
else t=1<<k;
dp[now][t]=max(dp[now][t],dp[pre][j]+get);
// printf("**%d\n",get);
}
}
now=!now;
pre=!pre;
}
for(i=0;i<=4096;i++) sum=max(sum,dp[pre][i]);
}
int main()
{
int t;
int loc[20];
scanf("%d",&t);
loc[2]=1;loc[4]=2;loc[8]=3;loc[16]=4;
score[0]=1;
for(int i=1;i<=4096;i++)
score[i]=score[i-1]*2;
while(t--)
{
scanf("%d",&n);
sum=0;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i]=loc[a[i]];
}
solve();
printf("%d\n",sum);
}
return 0;
}