题目描述
帕秋莉掌握了一种火属性魔法
由于钟爱扫雷游戏,帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图,她制造了很多烈焰,排在这条走廊内
现在帕秋莉告诉你一部分烈焰的分布情况,请你告诉她可能的情况有多少种
对于一个格子,里面会有以下几种字符:
0:这个格子没有烈焰,且其左右两个格子均没有烈焰
1:这个格子没有烈焰,且其左右两个格子中只有一个烈焰
2:这个格子没有烈焰,且其左右两个格子中均有烈焰
*:这个格子有烈焰
?:未告诉你本格情况
题解
很明显是一道dp的题目,我们考虑它的转移方程是怎么样的。由题目里的限制 可以得到,当前位置是否为烈焰与他前一位和后一位是否为烈焰都有关,并且当我们枚举到当前位置的时候前一位的前一位是没有用的,
所以我们设dp[i][j 0/1][k 0/1]表示当前在i为状态为j,i+1位的状态为k。所以dp[][][]转移方程就可以轻松的得到啦~
并且由于第0位,第n+1位都不可能为烈焰,所以我们在初始化和最后统计答案的时候要注意一下下
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 2e6 + 6; const int N = 1e3 + 4; const double eps = 1e-6; ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} char s[maxn]; int n; ll ans,dp[maxn][2][2]; int main(){ scanf("%s",s+1); n=strlen(s+1); dp[0][0][0]=dp[0][0][1]=1; for(int i=1;i<=n;i++){ if(s[i]=='0'){ dp[i][0][0]=dp[i-1][0][0]; } if(s[i]=='1'){ dp[i][0][1]=dp[i-1][0][0]; dp[i][0][0]=dp[i-1][1][0]; } if(s[i]=='2'){ dp[i][0][1]=dp[i-1][1][0]; } if(s[i]=='*'){ dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod; dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod; } if(s[i]=='?'){ dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%mod; dp[i][0][1]=(dp[i-1][1][0]+dp[i-1][0][0])%mod; dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod; dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod; } } printf("%lld\n",dp[n][0][0]+dp[n][1][0]); }