[zoj 3802] Easy 2048 Again상압 DP
5357 단어 dp
Time Limit: 2 Seconds
Memory Limit: 65536 KB
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?
Input
The 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.
Output
For each case, you should output an integer. The answer is the maximum of the total score which Dark_sun may get.
Sample Input
3
4
2 8 4 8
5
2 2 4 8 16
8
8 4 4 2 8 4 2 2
Sample Output
34
92
116
Hint
In 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
제목의 대의.
L 개의 수를 정하고 그 중에서 임의로 몇 개의 수를 정하다.점수를 최대로 하다.
점수 계산 방법은 가방에 넣은 숫자와 기초 점수를 사용하고 게임 2048의 규칙에 따라 매번 팀 꼬리를 눌러서 팀 꼬리의 개수가 같으면 팀 꼬리가 두 배로 변하고 대응하는 점수를 더한다.
최대치가 얼마냐고 물었다.
문제풀이의 방향
sum값은 최대 8192=2^13을 초과하지 않습니다
가방 실행 가능 상태는 단조로운 창고
10은 가방의 끝부분에 82개의 숫자가 있음을 나타낸다
스크롤 그룹 압력은 새로운 값(대열 끝의 숫자보다 작거나 같음)의 업데이트 상태를 압축할 수 있습니까? 압축할 수 없으면 단조로운 창고의 최대 값을 a[i]로 정하면 됩니다.
스크롤 그룹 저장 상태입니다.
매번 컴보의 점수를 계산한다.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
using namespace std;
int dp[2][10000];
int check3[10000];
int check(int x,int y)
{
int tmp=0;
while (x&y)
{
tmp+=y*2;
x-=y;
y*=2;
}
return tmp;
}
int main()
{
memset(check3,0,sizeof check3);
for (int j=1;j<=9000;j=j*2)
for (int i=1;i*j<=9000;i++)
{
check3[i*j]=j;
}
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(dp,0,sizeof dp);
int o;
for (int i=1;i<=n;i++)
{
int en=i&1;
int st=en^1;
for (int j=0;j<=8192;j++)
{
dp[en][j]=max(dp[st][j],dp[en][j]);
}
scanf("%d",&o);
for (int j=0;j<=8192;j++)
if (check3[j]<o){
dp[en][o]=max(dp[st][j]+o,dp[en][o]);
}
for (int j=0;j<=8192;j++)
if (dp[st][j])
{
if (check3[j]>=o){
dp[en][o+j]=max(dp[st][j]+o+check(j,o),dp[en][o+j]);
}
}
int ans=0;
for (int j=0;j<=8192;j++)
{
ans=max(dp[en][j],ans);
}
if (i==n) printf("%d
",ans);
}
}
return 0;
}
/*
3
4
2 8 4 8
5
2 2 4 8 16
8
8 4 4 2 8 4 2 2
*/좋은 웹페이지 즐겨찾기
