`
阿尔萨斯
  • 浏览: 4107710 次
社区版块
存档分类
最新评论

Codeforces 413D 2048(dp)

 
阅读更多

题目连接:Codeforces 413D 2048


题目大意:2048的游戏,两个相同的数x可以变成一个2*x,先给出n,表示在一个1*n的矩阵上面玩2048,规定每次向左移动,并且每次出现一个,给出序列n,表示出现的块的值,0表示既可以是2也可以是4,问说有多少种可能,使得游戏结束后的最大块的值大于等于2^k。


解题思路:dp[i][j][x]表示第i个位置,值为j,x表示先前有没有出现过大于2^k的数;

这种递增的情况可以直接表示为14(总和,以为后面的2,4如果变大,就肯定能和8想合在一起),然后总和%4就可以知道最后以为是否为2,用于考虑被阻隔的情况。


这种情况状态就为6,但是如果k仅为4的话,它是可以满足的,所以这里的第三维状态就是为了区分这种情况的,因为被阻隔后最后的状态可能不够2^k。


具体递推方程见代码。


#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2050;
const int MOD = 1e9+7;

int	n, k, s[N];
int dp[N][N][2];

int solve () {

	for (int i = 1; i <= n; i++) {
		if (s[i] == 2 || s[i] == 0) {
			for (int j = 0; j < N; j++) {
				int p = min(j + 2, 2049);
				dp[i][p][1] = (dp[i][p][1] + dp[i-1][j][1])%MOD;
				dp[i][p][0] = (dp[i][p][0] + dp[i-1][j][0])%MOD;
			}
		}

		if (s[i] == 4 || s[i] == 0) {
			for (int j = 0; j < N; j++) {
				int p = min(j + 4, 2049);

				if (j%4) {
					if (j >= (1<<k))
						dp[i][4][1] = (dp[i][4][1] + dp[i-1][j][0])%MOD;
					else
						dp[i][4][0] = (dp[i][4][0] + dp[i-1][j][0])%MOD;

					dp[i][4][1] = (dp[i][4][1] + dp[i-1][j][1])%MOD;
				} else {
					dp[i][p][0] = (dp[i][p][0] + dp[i-1][j][0])%MOD;
					dp[i][p][1] = (dp[i][p][1] + dp[i-1][j][1])%MOD;
				}
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < 2050; i++) {
		ans = (ans + dp[n][i][1])%MOD;
		if (i >= (1<<k))
			ans = (ans + dp[n][i][0])%MOD;
	}
	return ans;
}

int main () {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &s[i]);

	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
	printf("%d\n", solve());
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics