题意:一维扫雷,给出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,且下一个位置不是b......
阅读全文