「火」皇家烈焰

题意:问可以构成多少种情况
题解:都在代码里面
主要在于分类讨论
时间复杂度:

#include<bits/stdc++.h>
using namespace std;//雷=皇家火焰
long long dp[10000000][2];//表示从头开始到第i位,?为雷和不为雷的情况数(0,不为雷/1,为雷)
int mod = 1e9+7;
int main()
{
    string s;
    cin>>s;
    int n=s.length();
    s=" "+s;
    dp[0][0]=1;//初始情况下,假设s中无'?',即结果为输入的那一种
    for(int i=1; i<=n; i++)
    {
        if(s[i]=='0')
        {
            dp[i][0]=dp[i-1][0];//第i位为0,不为雷,那么第i-1必不为雷,
            //所以对于此时的第i位为雷数为0,不为雷数与第i-1位不为雷数相同
        }
        else if(s[i]=='2')
        {
            dp[i][0]=dp[i-1][1];//第i位为2,不为雷,那么第i-1必为雷,
            //所以对于此时的第i位为雷数为0,不为雷数与第i-1位为雷数相同
        }
        else if(s[i]=='1')////第i位为1,不为雷,那么存在左雷或者右雷,分情况讨论,dp时要无后效性,所以用i+1位判断
        {
            if(s[i+1]=='*')//左不为雷,右为雷
            {
                dp[i][0]=dp[i-1][0];
                //所以对于此时的第i位为雷数为0,不为雷数与第i-1位为雷数相同
            }

            else if(s[i+1]=='?')//右边不确定,所以可以为雷,也可以不为雷
            {
                dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
                //参考上述描述
            }
            else //s[i+1]=='0'//左为雷,右不为雷
            {
                dp[i][0]=dp[i-1][1];
                //所以对于此时的第i位为雷数为0,不为雷数与第i-1位为雷数相同
            }
            //if(s[i+1]=='2').......数据非法
        }
        //以上三种的的dp[i][1]均为0;
        else if(s[i]=='*')//本情况dp[i][0]=0
        {
            dp[i][1]=dp[i-1][0]+dp[i-1][1];
            dp[i][1]%=mod;
            //第i位为0,那么对于第i位来说不受字符串的影响
            //所以假设在第i位字符串结束时,那么对于到第i位存在的字符串的种类数为
            //第i-1位为雷数和不为雷数求和
        }
        else//s[i]=='?',对于第i位未知,然后分情况讨论
        {
            if(s[i-1]=='0')
            {
                //那么第i位锁定,不为雷
                dp[i][0]=dp[i-1][0];
            }
            else if(s[i-1]=='2')
            {
                //那么第i位锁定,为雷
                dp[i][1]=dp[i-1][0];
            }
            else if(s[i-1]=='1')
            {
//那么第i位如果为雷,那么第i-2位不为雷
                dp[i][1]=dp[i-2][0];
//那么第i位如果不为雷,那么第i-2位为雷
                dp[i][0]=dp[i-2][1];
            }
            else //s[i-1]=='*'和s[i-1]=='?',那么对于第i位不受前面i-1位限制
            {
                dp[i][0]=dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;
            }
        }
    }
    int ans=dp[n][1]+dp[n][0];//以第n位为结束的所有情况数
    ans%=mod;
    printf("%d",ans);
}