本文主要是介绍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;elsedp[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;
}
这篇关于Codeforces 413D 2048(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
