首页 > 代码库 > zoj3802：easy 2048 again（状压dp）
zoj3802：easy 2048 again（状压dp）
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 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]<<k; } state=((tmp<<k)*a[i])|(a[i]<<k); dp[i%2][state]=max(dp[i%2][state],dp[(i-1)%2][j]+score); //情况2 continue; } state=j|a[i]; score=a[i]; dp[i%2][state]=max(dp[i%2][state],dp[(i-1)%2][j]+score); //情况3 } } int ans=-1; for(int i=0;i<8192;i++) { ans=max(ans,dp[n%2][i]); } printf("%d\n",ans); } return 0;}
zoj3802：easy 2048 again（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。