「火」皇家烈焰 题解

明显动规求解。

因为每个点的情况之和其左右两边那个点有关，所以，我们只需知道一个点左右两个点的状态就可以算出这个点的情况了，那么我们考虑将一个点左右两个点的状态储存下来。
但是，仔细分析下，我们i这个点是由i-1这个状态转移过来的，那么，我们转移过来的时候，其实并不需要知道i-1这个点前面那个点的状态，所以，有部分的状态是亢余的。所以，我们可以只考虑记录一个点和其后面那个点的状态

我们如下规定：
0表示当前点和右边点都不是烈焰，1表示当前是烈焰，右边不是，2表示当前不是，右边是，3表示两个都是
(只是规定而已，你也可以其他顺序规定)

那么，我们在不考虑右边造成的影响的情况下(因为我们枚举到右边时自然会令右边的点符合要求，不符合的情况不会转移过去)
(设0表示不是烈焰，1表示是烈焰)
有如下情况：

当前点为'0':
那么左边和当前点和右边必然是0，那么转移就是:

当前点为'1':
那么两个情况，左边是0，右边是1和左边是1，右边是0。
那么转移就是:

当前点为'2':
那么左边和右边都是1，转移就是:

当前点为'*'
那么只要当前点为1，其他的都可以转移过来，即为：

当前点为'?'
那么当前点随便是什么，只要当前点和左边的转移过来的状态相同即可

(这部分是i为0)

(这部分是i为1)

然后中途记得取模就行了

最后，答案就是(因为右边没有点了，不能算作烈火)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1,mod=1e9+7;
int dp[N][4];//第i个格子及后边两个格子是否是烈焰的情况数
//0两个都不是,1这个是后面不是，2这个不是后面面是,3两个都是
int main(){
    string v;
    cin>>v;
    int len=v.size();
    dp[0][0]=dp[0][2]=1;//左边为空，当做非烈火
    for(int i=1;i<=len;++i){
        if(v[i-1]=='0'){
            dp[i][0]=dp[i-1][0];
        }
        if(v[i-1]=='1'){
            dp[i][0]=dp[i-1][1];
            dp[i][2]=dp[i-1][0];
        }
        if(v[i-1]=='2'){
            dp[i][2]=dp[i-1][1];
        }
        if(v[i-1]=='*'){
            dp[i][1]=dp[i][3]=(dp[i-1][2]+dp[i-1][3])%mod;
        }
        if(v[i-1]=='?'){
            dp[i][0]=dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod;
            dp[i][1]=dp[i][3]=(dp[i-1][2]+dp[i-1][3])%mod;
        }
    }
    int ans=(dp[len][0]+dp[len][1])%mod;
    printf("%d",ans);
    return 0;
}