【每日一题】「火」皇家烈焰

很明显的DP了，只要把状态能决定好，转移方程还是很好定下来的。
首先很容易能想到至少2维，dp[i][j]表示前i个合法的序列中，j为1时表示第i个有火，0就没火的合法序列总数。
但是这样是不够的，很明显可以发现，题面上说了，当前位会跟前一位和后一位都会有限制问题，因此还需要多加一维，dp[i][j][k]，k就表示它后一位是1有火或者0无火的合法序列总数。因为前一位可以从转移来限制，后一位就能通过k来限制，所以这样的状态就是足够的了。
然后再想想转移方程：

对于一个格子，里面会有以下几种字符：
0：这个格子没有烈焰，且其左右两个格子均没有烈焰
1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰
2：这个格子没有烈焰，且其左右两个格子中均有烈焰
*：这个格子有烈焰
？：未告诉你本格情况

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][0][1]+dp[i-1][1][1]
dp[i][1][1]=dp[i-1][0][1]+dp[i-1][1][1]

? 不知道情况，那就全部都转移一遍：

dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])
dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])
dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][1][0])
dp[i][0][1]=(dp[i-1][0][0]+dp[i-1][1][0])

只要捋清楚i j k的关系，转移方程还是很好想的。然后就开心的复制粘贴刚刚的情况代码，AC就完事了嗷！
记得初始化dp[0][0][1]=dp[0][0][0]=1。

#include<bits/stdc++.h>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char s[maxn];

ll dp[maxn][2][2];

int main(){
    scanf("%s",s+1);
    dp[0][0][0]=dp[0][0][1]=1;
    int n=strlen(s+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][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;
            dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][1][0])%mod;
            dp[i][0][1]=(dp[i-1][0][0]+dp[i-1][1][0])%mod;
        }
    }
    printf("%lld",dp[n][0][0]+dp[n][1][0]);
    return 0;
}