[火]皇家烈焰

题意：有n个格子排成一列
对于一个格子，里面会有以下几种字符：

0：这个格子没有烈焰，且其左右两个格子均没有烈焰

1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰

2：这个格子没有烈焰，且其左右两个格子中均有烈焰

*：这个格子有烈焰

？：未告诉你本格情况

求n个格子分布合理的情况数？

思路：dp

dp[i][0/1][0/1]表示前i位，当前位和下一位是（1）不是（0）烈焰的情况数

当s[i]='*'时， 该位是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])

当s[i]='0'时，上一位、当前位和下一位都得是0：
dp[i][0][0]=dp[i-1][0][0]

当s[i]='1'时，上一位或下一位有一个是1：
dp[i][0][1]=dp[i-1][0][0]
dp[i][0][0]=dp[i-1][1][0]

当s[i]='2'时，上一位和下一位都是1,当前位为0：
dp[i][0][1]=dp[i-1][1][0]；

当s[i]='?'时，上一位、当前位和下一位都随意：
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])

初值为dp[0][0][0] =1,dp[0][0][1] = 1

代码：

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

ll dp[1000005][3][3];
int a[1000005];

int main()
{
    char s[1000005];
    int n;
    scanf("%s",(s+1));
    n=strlen(s+1);
    dp[0][0][1]=1;
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
       if(s[i]=='*')
       {
           dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%inf;
           dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%inf;
       }
       else if(s[i]=='0')
       {
           dp[i][0][0]=dp[i-1][0][0];
       }
       else if(s[i]=='1')
       {
           dp[i][0][1]=dp[i-1][0][0];
           dp[i][0][0]=dp[i-1][1][0];
       }
       else if(s[i]=='2')
       {
           dp[i][0][1]=dp[i-1][1][0];
       }
       else
       {
           dp[i][0][1]=(dp[i-1][1][0]+dp[i-1][0][0])%inf;
           dp[i][1][1]=(dp[i-1][1][1]+dp[i-1][0][1])%inf;
           dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%inf;
           dp[i][1][0]=(dp[i-1][1][1]+dp[i-1][0][1])%inf;
       }
    }
    ll z;
    if(s[n]=='?')
    {
        z=(dp[n][1][0]+dp[n][0][0])%inf;
    }
    else if(s[n]=='1'||s[n]=='0'||s[n]=='2')
    {
        z=(dp[n][0][0])%inf;
    }
    else
    {
        z=(dp[n][1][0])%inf;
    }
    cout << z <<endl;
    return 0;
}