首页 > 代码库 > ZOJ3802 Easy 2048 Again （状压DP）
ZOJ3802 Easy 2048 Again （状压DP）
ZOJ Monthly, August 2014 E题
ZOJ月赛 2014年8月 E题
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5334
Dark_sun knows that on a single-track road (which means once he passed this area, he cannot come back again), there are some underground treasures on each area of the road which has the value of 2, 4, 8 or 16. Dark_sun can decide whether to dig them or not in order to get the highest score. The calculation rule of the total score is similar to the game Flappy 2048. Dark_sun‘s bag is like a queue. When he gets a treasure, the treasure will be pushed back into the end of the bag. And the score will add the value of the treasure. For example, when there are treasures on the road in the order of {2, 8, 4, 8} and if Dark_sun decides to dig all of them, he will get the final score of 2+8+4+8=22. And his bag will finally become the sequence of {2, 8, 4, 8}. If the adjacent treasures in the Dark_sun‘s bag have the same value, they will mix into a bigger treasure which has the value of their sum (the double value of the previous one). And Dark_sun will get a combo score of the value of bigger treasure. For example in the previous case, if Dark_sun decides to dig only the {2, 8, 8} treasure in sequence. He will get the basic score of 18(2+8+8). And when the last treasure (value 8) is pushed back into his bag, his bag will turn {2, 8, 8} into {2, 16} and he will get a bonus score of 16. And his final score will become 18+16=34 (which is the best strategy in this case.) Notice that the treasures mix to the bigger one automatically when there are the same adjacent treasures. For example, when there are treasures of {2, 2, 4, 8, 16} on the road, and if Dark_sun decides to dig all of them, he will get the basic score of 32(2+2+4+8+16) and a bonus score of 60(4+8+16+32). At last he will get the total score of 92 and the bag becomes {32}. Now, Dark_sun wants to get the highest score (no matter what‘s the treasure in his bag), can you tell him the what‘s the highest score? InputThe first line is an integer n, which is the case number. In each case, the first line is an integer L, which is the length of the road.(0 < L ≤ 500) The second line contains L integers which can only be 2, 4, 8 or 16. This means the value of treasure on each area of the road. OutputFor each case, you should output an integer. The answer is the maximum of the total score which Dark_sun may get. Sample Input342 8 4 852 2 4 8 1688 4 4 2 8 4 2 2 Sample Output3492116 HintIn the third sample case, Dark_sun will choose {8,4,4,8,4,2,2}. Firstly, the first three treasures will be combined to 16 and then the {16,8,4,2,2} will become 32. And he will get the basic score 32(8+4+4+8+4+2+2) and the bonus score 84(8+16+4+8+16+32). Author: Ni, Xinyi Source: ZOJ Monthly, August 2014 |
题意：类似“Flappy 2048”，输入N个元素，元素是2 4 8 16四个数之一。从左到右飞，遇到一个数可以选择取或不取，取的话存到背包里（入栈），若背包里有相邻的相同的数字，会立刻自动合成他们的和。得分是取一个数可以得到这个数数值的分，合成一个数可以得到这个数数值的分，求最高总分。（N<=500）
题解：状压DP。
N<=500，500个16合起来能得8000,2^13=8192，所以最多只能合到4096。2,4,8......4096，即2^1~2^12，只有12种数。思考如何得到最优解，对一个数是否加入背包，是和背包中的若干个元素有关的，不只和最后一个元素有关（因为可能会连环合，例如背包里是8 4 2，现在加入一个2，啪啪啪就合成16了）。所以我们要把背包里的若干个元素也考虑进去，想成一个状态。但是背包里所有元素都考虑的话，有12^500种状态，简直尿，所以再想想。
和新加入的数有关的背包里的元素，其实就是最后的递减序列，因为只有递减的才可能因为新加入的数而合成新数，如果出现一个递增的，之前的数就都没办法再合成了，可以不用管，不用算进状态里。这样，我们想办法用小空间存储递减序列的必要信息，可以用类似集合的存法，就是每个二进制位代表一个元素是否在集合中。
例如第1位代表是否有2，第2位代表是否有4，第3位代表是否有8……第12位代表是否有4096。这样，只用12位二进制数就能表示这个递减序列的信息（因为是递减序列嘛，顺序已经定了，只用存是否存在就行）。状态就可以用0~4095表示出来。
观察如何状态转移，也就是合并规则。
不加入当前元素，直接f[i][j]=max( f[i][j] , f[i-1][j])
加入当前元素：当递减序列里没有比当前元素小的元素，才可以合并；当递减序列里有比当前元素小的，就不能合并，而且新加入的元素作为新的递减序列（新的递减序列只包括这一个元素了）。
具体动规代码（滚动数组）：
1 int now=0,pre=1; 2 mf1(f); 3 f[pre][0]=0; 4 for(i=1; i<=n; i++) { 5 for(j=0; j<4096; j++) { 6 if(f[pre][j] != -1) { 7 f[now][j]=max(f[now][j],f[pre][j]);///不选当前点 8 9 int t=j;///状态10 k=a[i]-1;///a[i]代表的位的位置，第k位11 int q=(1<<k) -1 ;///q为( 比k低的位数全是1 )的数12 int get=p2[a[i]];///新得分13 if((t&q)==0) {///如果比k低的位全是0，才能合并14 while( (t & (1<<k)) ) {///合并，数之前有多少个连续的1，统计合并得分15 get+=p2[k+2];16 k++;17 }18 q=(1<<k) -1;19 t&=~q;///把比k低的位数全变成0，怕不怕20 t|=1<<k;21 }else t=1<<k;///不能合并，产生新递减序列，只有k位是122 f[now][t]=max( f[now][t] , f[pre][j]+get );23 }24 }25 swap(now,pre);26 }
最后找f[n][j]的最大值就行了。
（怕了，比赛的时候直接看样例，没看题，以为是一维的2048，不会自动合并，我可以选后面的先合……逗乐！居然是Flappy2048，谁会玩那种逗游戏啊！看来以后还是要看题……然后我也没想到状压，其实还是挺简单的，只是我状压做得少/.\）
（这题不滚动数组，用[501][4096]也不会MLE，但是时间一秒六……大概数据组数多，清零耗时太多。滚动数组只要100ms左右）
全代码（滚动数组）：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll long long14 #define usll unsigned ll15 #define mz(array) memset(array, 0, sizeof(array))16 #define mf1(array) memset(array, -1, sizeof(array))17 #define minf(array) memset(array, 0x3f, sizeof(array))18 #define REP(i,n) for(i=0;i<(n);i++)19 #define FOR(i,x,n) for(i=(x);i<=(n);i++)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) prllf("%d\n",x);24 #define RE freopen("D.in","r",stdin)25 #define WE freopen("1biao.out","w",stdout)26 #define mp make_pair27 #define pb push_back28 const int maxn=511;29 int p2[14];30 31 int n;32 int a[maxn];33 34 int f[2][4096];///f[i][j]，j为状态，集合，j二进制第i位为1表示存在元素2^i。35 ///最多合出4096，是2^12，所以开12位来存，2^12=4096。36 int farm() {37 int i,j,k;38 int now=0,pre=1;39 mf1(f);40 f[pre][0]=0;41 for(i=1; i<=n; i++) {42 for(j=0; j<4096; j++) {43 if(f[pre][j] != -1) {44 f[now][j]=max(f[now][j],f[pre][j]);///不选当前点45 46 int t=j;///状态47 k=a[i]-1;///a[i]代表的位的位置，第k位48 int q=(1<<k) -1 ;///q为( 比k低的位数全是1 )的数49 int get=p2[a[i]];///新得分50 if((t&q)==0) {///如果比k低的位全是0，才能合并51 while( (t & (1<<k)) ) {///合并，数之前有多少个连续的1，统计合并得分52 get+=p2[k+2];53 k++;54 }55 q=(1<<k) -1;56 t&=~q;///把比k低的位数全变成0，怕不怕57 t|=1<<k;58 }else t=1<<k;///不能合并，产生新递减序列，只有k位是159 f[now][t]=max( f[now][t] , f[pre][j]+get );60 }61 }62 swap(now,pre);63 }64 int re=0;65 for(j=0; j<4096; j++) {66 re=max(re,f[pre][j]);67 }68 return re;69 }70 71 int l2[17];72 int main() {73 int T,i,x;74 l2[2]=1;75 l2[4]=2;76 l2[8]=3;77 l2[16]=4;///l2[i]=log2(i)78 p2[0]=1;79 for(i=1; i<=13; i++)///最多就把500个16合在一起（其实不到），8000，2^13=819280 p2[i]=p2[i-1]*2;///p2[i]=pow(2,i)81 scanf("%d",&T);82 while(T--) {83 scanf("%d",&n);84 for(i=1; i<=n; i++) {85 scanf("%d",&x);86 a[i]=l2[x];87 }88 printf("%d\n",farm());89 }90 return 0;91 }
ZOJ3802 Easy 2048 Again （状压DP）