题目链接:https://ac.nowcoder.com/acm/contest/2272/J
题目大意:
我的思路是用f[i][j][k][w]:表示前i个格子
j:前一个格子有没有
k:这个格子有没有
w:下一个格子有没有
的情况数。
状态表示冗余了。我们用f[i][j][k]表示前i个格子
j:这个格子有没有
k:下一个格子有没有
就可以了。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;
char s[1000005];
LL f[1000005][2][2]={0};
int main()
{
scanf("%s", s+1);
int n=strlen(s+1);
f[0][0][0]=1;
f[0][0][1]=1;
for(int i=1; i<=n; i++){
if(s[i]=='0'){
f[i][0][0]+=f[i-1][0][0];
f[i][0][0]%=mod;
}
if(s[i]=='1'){
f[i][0][0]+=f[i-1][1][0];
f[i][0][1]+=f[i-1][0][0];
f[i][0][0]%=mod;
f[i][0][1]%=mod;
}
if(s[i]=='2'){
f[i][0][1]+=f[i-1][1][0];
f[i][0][1]%=mod;
}
if(s[i]=='*'){
f[i][1][0]+=(f[i-1][1][1]+f[i-1][0][1]);
f[i][1][1]=f[i][1][0];
f[i][1][0]%=mod;
f[i][1][1]%=mod;
}
if(s[i]=='?'){
f[i][1][0]+=(f[i-1][1][1]+f[i-1][0][1]);
f[i][1][1]+=f[i][1][0];
f[i][0][0]+=(f[i-1][1][0]+f[i-1][0][0]);
f[i][0][1]+=f[i][0][0];
f[i][1][0]%=mod;
f[i][1][1]%=mod;
f[i][0][0]%=mod;
f[i][1][0]%=mod;
}
}
printf("%lld\n", (f[n][0][0]+f[n][1][0])%mod);
return 0;
}