本文主要是介绍CF - 404 - D. Minesweeper 1D（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一维扫雷，给出0, 1, 2, ?, *，问符合规则的地图有多少种 (长度：1 ≤ n ≤ 10^6)？
题目链接：http://codeforces.com/contest/404/problem/D
——>>怎么想呢？
看CF的代码看出了这样的想法：
设d[i][j]表示前i个位置（其中第i个位置是类型jj）的正确放置数。。
对于一个位置，共有3种类型：
0 ： 该位置不是bomb，且下一个位置也不是bomb；
1 ： 该位置不是bomb，且下一个位置是bomb；
2 ： 该位置是bomb。
那么，可以得到状态转移方程：
设现在的位置是i，
一、如果是输入的0，
说明这个位置不是bomb，且下一个位置不是bomb，所以只会更新d[i][0]，同时，上一个位置也不会是bomb，于是得：
d[i][0] = d[i-1][0];
二、如果是输入的1，
说明这个位置不是bomb，但下一个位置可能是bomb，如果下一个位置是bomb，那么上一个位置不会是bomb，则：
d[i][1] = d[i-1][0];
如果下一个位置不是bomb，那么上一个位置是bomb，则：
d[i][0] = d[i-1][2];
三、如果输入的是2，
说明这个位置不是bomb，下一个位置是bomb，所以只会更新d[i][1]，且上一个位置是bomb，于是得：
d[i][1] = d[i-1][2];
四、如果输入的是*，
说明这个位置是bomb，上一个位置可以是bomb，也可以是1，则：
d[i][2] = d[i-1][2] + d[i-1][1];
五、如果输入的是?，说明以上情况都可以，所以情况的数目都要加起来。。
************************************************************************
可以发现，d的第一维可以省略，用滚动数组的思想。。
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 1000000 + 10;
const int mod = 1000000000 + 7;char s[maxn];int main()
{while(scanf("%s", s) == 1) {long long d[] = {1, 1, 0};for(int i = 0; s[i]; i++) {long long t[] = {0, 0, 0};if(s[i] == '0' || s[i] == '?') t[0] += d[0];if(s[i] == '1' || s[i] == '?') {t[1] += d[0];t[0] += d[2];}if(s[i] == '2' || s[i] == '?') t[1] += d[2];if(s[i] == '*' || s[i] == '?') t[2] += d[2] + d[1];for(int j = 0; j < 3; j++) d[j] = t[j] % mod;}printf("%I64d\n", (d[0] + d[2]) % mod);}return 0;
}
这篇关于CF - 404 - D. Minesweeper 1D（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
