題目鏈接：點擊查看

題目大意：給出一個字符串表示掃雷游戲，其中：

0：這個格子沒有烈焰，且其左右兩個格子均沒有烈焰

1：這個格子沒有烈焰，且其左右兩個格子中只有一個烈焰

2：這個格子沒有烈焰，且其左右兩個格子中均有烈焰

*：這個格子有烈焰

？：未告訴你本格情況

要求計算一共有多少種方案可以滿足給出的情況

題目分析：因為看到結果要對1e9+7取模，很大概率是一個線性dp，那么我們需要考慮一下該怎么設計轉移方程，因為每次轉移的狀態都是從前向后轉移的，所以我們開一個dp[2][2][2]的數組就足夠儲存相鄰兩個狀態了，但因為這個題目給的內存足夠，所以我們可以直接每個狀態都儲存一遍，方便理解也更好寫了，其中對于dp[i][j][k]，代表的是截止到第i格為止，j：代表當前格子有無烈焰，k：代表下一格子有無烈焰，這樣轉移方程也就比較好寫了：

當前格子為0：dp[i][0][0]=dp[i-1][0][0]

當前格子為1：dp[i][0][1]=dp[i-1][0][0],dp[i][0][0]=dp[i-1][1][0]

當前格子為2：dp[i][0][1]=dp[i-1][1][0]

當前格子為*：dp[i][1][0]=dp[i][1][1]=dp[i-1][0][1]+dp[i-1][1][1]

當前格子為?：dp[i][1][1]=dp[i][1][0]=dp[i-1][0][1]+dp[i-1][1][1],dp[i][0][0]=dp[i][0][1]=dp[i-1][0][0]+dp[i-1][1][0]

初始化的話，讓dp[0][0][0]=dp[0][0][1]=1就好了

雖然看著很麻煩，但仔細想一下無非就只有這么多情況，按照公式實現就好了

最后答案是dp[n][0][0]+dp[n][1][0]

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod=1e9+7;LL dp[N][2][2];//dp[i][j][k]:截止到i為止，j:當前位置有無炸彈，k:下一個位置有無炸彈 char s[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%s",s+1);int 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]%mod;}else if(s[i]=='1'){dp[i][0][0]=dp[i-1][1][0]%mod;dp[i][0][1]=dp[i-1][0][0]%mod;}else if(s[i]=='2'){dp[i][0][1]=dp[i-1][1][0]%mod;}else if(s[i]=='*'){dp[i][1][1]=dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;}else if(s[i]=='?'){dp[i][0][1]=dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%mod;dp[i][1][0]=dp[i][1][1]=(dp[i-1][1][1]+dp[i-1][0][1])%mod;}}printf("%lld\n",(dp[n][0][0]+dp[n][1][0])%mod);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 「火」皇家烈焰(线性dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。