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 <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
int dp[][];
int a[];
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=;i<=n;i++)
{
scanf("%d",a+i);
}
memset(dp,-,sizeof(dp));
dp[][]=;
dp[][a[]]=a[];
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
if(dp[(i-)%][j]==-)
{
continue;
}
dp[i%][j]=max(dp[i%][j],dp[(i-)%][j]); //不取
if(j&(a[i]-))
{
dp[i%][a[i]]=max(dp[i%][a[i]],dp[(i-)%][j]+a[i]); //情况1
continue;
}
int state,score;
if(j&a[i])
{
int tmp=j/a[i],k=;
score=a[i];
while(tmp%)
{
k++;
tmp/=;
score+=a[i]<<k;
}
state=((tmp<<k)*a[i])|(a[i]<<k);
dp[i%][state]=max(dp[i%][state],dp[(i-)%][j]+score); //情况2
continue;
}
state=j|a[i];
score=a[i];
dp[i%][state]=max(dp[i%][state],dp[(i-)%][j]+score); //情况3
}
}
int ans=-;
for(int i=;i<;i++)
{
ans=max(ans,dp[n%][i]);
}
printf("%d\n",ans);
}
return ;
}