「火」皇家烈焰

前面的碎碎念，每次每日一题看完题目感觉没思路就忍不住去瞄雨巨的题解，看完就感觉啥都会了，老这样是不是没提高啊

思路

dp[ i ][ 0 ][ 0 ]第i个位置 无火，第i+1个位置 无 火
dp[ i ][ 0 ][ 1 ]第i个位置 无 火，第i+1个位置 有 火
dp[ i ][ 1 ][ 0 ]第i个位置 有 火，第i+1个位置 无 火
dp[ i ][ 1 ][ 1 ]第i个位置 有 火，第i+1个位置 有 火
这样就很容易可以写出状态转移方程了，都在代码里我就不在这写了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1000005;

ll dp[maxn][3][3];

int main(){
    string s;
    cin>>s;
    s = " " + s;
    dp[0][0][0] = dp[0][0][1] = 1;
    for(int i = 1 ; i < s.size() ; ++i){
        if(s[i]=='0'){
            dp[i][0][0] = dp[i-1][0][0];//左右均没有火，那i-1，i，i+1都是0
        }
        else if(s[i] == '1'){// 0 0 1或 1 0 1，其他为0
            dp[i][0][0] = dp[i-1][1][0];
            dp[i][0][1] = dp[i-1][0][0];
        }
        else if(s[i] == '2'){
            dp[i][0][1] = dp[i-1][1][0];
        }
        else 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];//右边有火无火的情况都一样
        }
        else{
            dp[i][0][0] = (dp[i-1][1][0]+dp[i-1][0][0])%mod;//?情况满足当前位置情况就好
            dp[i][0][1] = dp[i][0][0];
            dp[i][1][0] = (dp[i-1][0][1]+dp[i-1][1][1])%mod;
            dp[i][1][1] = dp[i][1][0];
        }
    }
        cout<<(dp[s.size()-1][1][0]+dp[s.size()-1][0][0])%mod<<endl;//s.size()位置不可能是有火的
}

写这个题解主要是吐槽一下