鏈接：
「火」皇家烈焰

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

帕秋莉掌握了一種火屬性魔法

由于鐘愛掃雷游戲，帕秋莉把自己圖書館前的走廊看作一個一維的掃雷地圖，她制造了很多烈焰，排在這條走廊內(nèi)

現(xiàn)在帕秋莉告訴你一部分烈焰的分布情況，請你告訴她可能的情況有多少種

對于一個格子，里面會有以下幾種字符：

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

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

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

*：這個格子有烈焰

？：未告訴你本格情況

輸入描述:

一個字符串

輸出描述:

輸出一行，一個整數(shù)表示答案，對1e9+7取模

示例1
輸入

?1?

輸出

2

說明
已知第二個格子左右有一個烈焰

因此可能的情況有10和01，顯然其他情況都無法滿足已知條件的要求
備注:
字符串的長度為n
對于30%的數(shù)據(jù)，n≤20
對于60%的的數(shù)據(jù)，n≤1,000
對于100%的數(shù)據(jù)，n≤1,000,000

題解：

乍一看以為是掃雷。仔細(xì)一看為什么又是dp（每日一題好愛出dp，而我dp又是渣渣）

在其他大佬那吸取知識之后，寫出自己的理解：

我們仔細(xì)看題可以看出，每個點什么情況其實都與兩側(cè)的點息息相關(guān)，我可以通過一個點算出兩側(cè)點的狀態(tài)，也可以根據(jù)兩側(cè)狀態(tài)來反推中間的點。
但是我們狀態(tài)轉(zhuǎn)移的順序是從左到右，我們在轉(zhuǎn)移過程中，考慮第i點時，i-1之前的點狀態(tài)都是固定的，所以我們只需要考慮當(dāng)前點i與之后一個點i+1的狀態(tài)。
在第i點時，i+1可能也有了要求，所以不滿足情況的就不用轉(zhuǎn)移狀態(tài)。
dp[i][0/1/2/3]：

0表示i與i+1都不是火
1表示i是火，i+1不是火
2表示i不是火，i+1是
3表示i和i+1都是火

對照題目給出的狀態(tài)，

0：這個格子沒有烈焰，且其左右兩個格子均沒有烈焰1：這個格子沒有烈焰，且其左右兩個格子中只有一個烈焰2：這個格子沒有烈焰，且其左右兩個格子中均有烈焰*：這個格子有烈焰？：未告訴你本格情況

具體情況如下：

if（i = = 0)
說明i-1，i，i+1都沒有火,i 的狀態(tài)就是等同于i-1的狀態(tài)都是0（即本身與右邊都不是火）
轉(zhuǎn)移方程：f [i ] [ 0 ] = f [ i - 1 ] [ 0 ]

if（i = = 1）
i不是火，但是i的周圍有一個火
如果左邊是火,那么右邊就不是火，那i就滿足狀態(tài)0，i-1就滿足狀態(tài)1：f[i][0]=f[i-1][1]
如果右邊是火，左邊就不是火，那么i就滿足狀態(tài)2，i-1就滿足狀態(tài)0：f [ i ][ 2 ] = f [ i - 1 ] [ 0]

if（i = = 2）
左右均為火，那么i-1是火，i不是火，i+1是火，i就滿足狀態(tài)2: f [ i ] [ 2 ] =f [ i-1 ] [ 1 ]

if（i = = *）
當(dāng)前i為火，I+1有兩種情況，
一個是i+1位火：
f [ i ] [ 3 ]= f [ i - 1 ] [ 2 ] + f [ i - 1 ] [ 3 ]
i+1不是火：
f [ i ] [ 1 ] = f [ i - 1 ] [ 2 ] + f [ i - 1 ] [ 3 ]

if（i = = ?）
當(dāng)前點未知，我們就要考慮所有情況
i為火，i不為火，i+1為火，i+1不為火
四種情況：
i與i+1都不是火：
f [ i ] [0 ] = f[ i - 1 ][ 0 ] + f [i - 1 ] [ 1 ]

i不是，i+1是火
f [ i ] [ 2 ] = f [ i - 1 ] [ 0 ] + f [ i - 1 ] [ 1 ]

i是火，i+1不是
f [ i ] [ 1 ] = f [ i - 1 ] [ 2 ] + f [i - 1 ] [ 3 ]

i和i+1都是火
f [ i ] [ 3 ] = f [ i - 1 ] [ 2 ] + f [ i - 1 ][ 3 ]

到最后一個點i，i后面沒有點了，相當(dāng)于i+1不是火
答案就是
i是火與不是火了兩種情況加一起
f [ i ] [ 0 ] + f [ i ] [ 1 ]
此時i=地圖長度

對了前往不要忘了取模mod

結(jié)合我講的，在代碼里面一條一條對應(yīng)

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+1,mod=1e9+7; int f[maxn][7]; char s[maxn]; int main() {f[0][0]=f[0][2]=1; cin>>s;int len=strlen(s);for(int i=1;i<=len;++i){if(s[i-1]=='0'){f[i][0]=f[i-1][0];}else if(s[i-1]=='1'){f[i][0]=f[i-1][1];f[i][2]=f[i-1][0];}else if(s[i-1]=='2'){f[i][2]=f[i-1][1];}else if(s[i-1]=='*'){f[i][1]=(f[i-1][2]+f[i-1][3])%mod;f[i][3]=(f[i-1][2]+f[i-1][3])%mod;}else if(s[i-1]=='?'){f[i][0]=(f[i-1][0]+f[i-1][1])%mod;f[i][2]=(f[i-1][0]+f[i-1][1])%mod;f[i][1]=(f[i-1][2]+f[i-1][3])%mod;f[i][3]=(f[i-1][2]+f[i-1][3])%mod;}}cout<<(f[len][0]+f[len][1])%mod;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【每日一题】5月7日题目精讲 「火」皇家烈焰的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。