题目连接: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;
}
分享到:
相关推荐
Codeforces 1925D Good Trip 题解
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Educational Codeforces Round 157D. XOR Construction
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
codeforces每日一练。 题意: 有n张卡片,卡片上的数字就是分数,比如说甲乙两人抽卡,三局两胜,一局得分高的胜,求在甲赢了两局的情况下乙赢了第三局且总分比甲高的概率。 思路: 数据1e3,很明显的On^2算法,所以...
Some of the Codeforces problems codes
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
codeforces-js Codeforces JS