「火」皇家烈焰

这是一道动态规划的题。

题意:给出一个长度为n的字符串，n最大1000000。 每个字符代表一种特殊含义。

0：这个格子没有烈焰，且其左右两个格子均没有烈焰
1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰
2：这个格子没有烈焰，且其左右两个格子中均有烈焰
*：这个格子有烈焰
？：未告诉你本格情况

求所有的方案数

分析: 可以发现，第i位方案数，和前一位和后一位有关系。 前一位可以通过转移方程来解决，所以还剩下当前位i、当前位i是否有火、i+1位是否有火。

所以我们需要一个三维数组来表示dp

dp[i][0/1][0/1]

i:表示第i位
第一个[0/1]: 表示第i位有没有火，有火就用1来表示，没火就用0来表示
第二个[0/1]: 表示第i+1位有没有火，有火就用1来表示，没火就用0来表示

然后初始化dp[0][0][0],dp[0][0][1] 的方案数位1 。这是显然的。

1、当字符为0的时候，代表这个格子没有烈焰，且其左右两个格子均没有烈焰。
所以 dp[i][0][0]+=dp[i-1][0][0]

2、当字符为1的时候，代表这个格子没有烈焰，且其左右两个格子中只有一个烈焰。
所以我们就可以分2中情况讨论，第一种就是左边格子有火焰 :dp[i][0][0]+=dp[i-1][1][0]
第二种就是右边格子有火焰 :dp[i][0][1]+=dp[i-1][0][0]
.......

最后答案就是 dp[n][0][0]+dp[n][1][0]。

剩下的情况大家自己去分类讨论下。

最后注意要开long long。不要忘记取mod。

AC代码: (供参考)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define PI 3.14159265358979323846

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const int N=1000000+100;

char s[N];

ll dp[N][2][2];//  dp[i][0/1][0/1] 表示当前第i位有没有火焰和第i+1位有没有火焰 

int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    dp[0][0][0]=dp[0][0][1]=1;
    for(int i=1;i<=len;i++)
    {
        if(s[i]=='0')
        {//表示第i位没有火焰，并且左右都没有火焰 
            dp[i][0][0]+=dp[i-1][0][0];  
            dp[i][0][0]%=mod;
        }
        else if(s[i]=='1')
        {
            dp[i][0][1]+=dp[i-1][0][0];
            dp[i][0][1]%=mod;

            dp[i][0][0]+=dp[i-1][1][0];
            dp[i][0][0]%=mod;
        }
        else if(s[i]=='2')
        {
            dp[i][0][1]+=dp[i-1][1][0];
            dp[i][0][1]%=mod;
        }
        else if(s[i]=='*')
        {
            dp[i][1][0]+=dp[i-1][1][1];
            dp[i][1][0]%=mod;

            dp[i][1][0]+=dp[i-1][0][1];
            dp[i][1][0]%=mod;

            dp[i][1][1]+=dp[i-1][1][1];
            dp[i][1][1]%=mod;

            dp[i][1][1]+=dp[i-1][0][1];
            dp[i][1][1]%=mod;
        }
        else
        {
            dp[i][0][0]+=dp[i-1][0][0];  
            dp[i][0][0]%=mod;
            //-------------------------------

            dp[i][0][1]+=dp[i-1][0][0];
            dp[i][0][1]%=mod;

            dp[i][0][0]+=dp[i-1][1][0];
            dp[i][0][0]%=mod;

            //-------------------------------

            dp[i][0][1]+=dp[i-1][1][0];
            dp[i][0][1]%=mod;

            //-------------------------------

            dp[i][1][0]+=dp[i-1][1][1];
            dp[i][1][0]%=mod;

            dp[i][1][0]+=dp[i-1][0][1];
            dp[i][1][0]%=mod;

            dp[i][1][1]+=dp[i-1][1][1];
            dp[i][1][1]%=mod;

            dp[i][1][1]+=dp[i-1][0][1];
            dp[i][1][1]%=mod;
        }
    } 
    printf("%lld\n",(dp[len][0][0]+dp[len][1][0])%mod);
    return 0;
}