这是一道动态规划的题。
题意:给出一个长度为n的字符串,n最大1000000。 每个字符代表一种特殊含义。
0:这个格子没有烈焰,且其左右两个格子均没有烈焰
1:这个格子没有烈焰,且其左右两个格子中只有一个烈焰
2:这个格子没有烈焰,且其左右两个格子中均有烈焰
*:这个格子有烈焰
?:未告诉你本格情况
求所有的方案数
分析: 可以发现,第i位方案数,和前一位和后一位有关系。 前一位可以通过转移方程来解决,所以还剩下当前位i、当前位i是否有火、i+1位是否有火。
所以我们需要一个三维数组来表示dp
dp[i][0/1][0/1]
i:表示第i位
第一个[0/1]: 表示第i位有没有火,有火就用1来表示,没火就用0来表示
第二个[0/1]: 表示第i+1位有没有火,有火就用1来表示,没火就用0来表示
然后初始化dp[0][0][0],dp[0][0][1] 的方案数位1 。这是显然的。
1、当字符为0的时候,代表这个格子没有烈焰,且其左右两个格子均没有烈焰。
所以 dp[i][0][0]+=dp[i-1][0][0]
2、当字符为1的时候,代表这个格子没有烈焰,且其左右两个格子中只有一个烈焰。
所以我们就可以分2中情况讨论,第一种就是左边格子有火焰 :dp[i][0][0]+=dp[i-1][1][0]
第二种就是右边格子有火焰 :dp[i][0][1]+=dp[i-1][0][0]
.......
最后答案就是 dp[n][0][0]+dp[n][1][0]。
剩下的情况大家自己去分类讨论下。
最后注意要开long long。不要忘记取mod。
AC代码: (供参考)
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } const int N=1000000+100; char s[N]; ll dp[N][2][2];// dp[i][0/1][0/1] 表示当前第i位有没有火焰和第i+1位有没有火焰 int main() { scanf("%s",s+1); int len=strlen(s+1); dp[0][0][0]=dp[0][0][1]=1; for(int i=1;i<=len;i++) { if(s[i]=='0') {//表示第i位没有火焰,并且左右都没有火焰 dp[i][0][0]+=dp[i-1][0][0]; dp[i][0][0]%=mod; } else if(s[i]=='1') { dp[i][0][1]+=dp[i-1][0][0]; dp[i][0][1]%=mod; dp[i][0][0]+=dp[i-1][1][0]; dp[i][0][0]%=mod; } else if(s[i]=='2') { dp[i][0][1]+=dp[i-1][1][0]; dp[i][0][1]%=mod; } else if(s[i]=='*') { dp[i][1][0]+=dp[i-1][1][1]; dp[i][1][0]%=mod; dp[i][1][0]+=dp[i-1][0][1]; dp[i][1][0]%=mod; dp[i][1][1]+=dp[i-1][1][1]; dp[i][1][1]%=mod; dp[i][1][1]+=dp[i-1][0][1]; dp[i][1][1]%=mod; } else { dp[i][0][0]+=dp[i-1][0][0]; dp[i][0][0]%=mod; //------------------------------- dp[i][0][1]+=dp[i-1][0][0]; dp[i][0][1]%=mod; dp[i][0][0]+=dp[i-1][1][0]; dp[i][0][0]%=mod; //------------------------------- dp[i][0][1]+=dp[i-1][1][0]; dp[i][0][1]%=mod; //------------------------------- dp[i][1][0]+=dp[i-1][1][1]; dp[i][1][0]%=mod; dp[i][1][0]+=dp[i-1][0][1]; dp[i][1][0]%=mod; dp[i][1][1]+=dp[i-1][1][1]; dp[i][1][1]%=mod; dp[i][1][1]+=dp[i-1][0][1]; dp[i][1][1]%=mod; } } printf("%lld\n",(dp[len][0][0]+dp[len][1][0])%mod); return 0; }