题目描述

难度分:$1900$

输入一个长度在$[1,10^6]$内的字符串，由五种字符*?012组成，表示一个一维扫雷游戏的局面。

其中*表示雷，数字表示左右相邻位置有多少个雷。

把?替换成*012中的一个，可以得到多少个合法的局面？结果可能很大，对其模上$10^9+7$再输出。

输入样例$1$

?01???

输出样例$1$

4

输入样例$2$

?

输出样例$2$

2

输入样例$3$

**12

输出样例$3$

0

输入样例$4$

1

输出样例$4$

0

算法

动态规划

这个题一看就差不多能确定是DP问题，但是状态定义非常难想。

状态定义

$f[i][j]$表示考虑$[1,i]$，$j=2$表示$i+1$位置是雷，$j \leq 1$时表示$i+1$位置不是雷，$j=0$表示$i$位置不是雷，$j=1$表示$i$位置是雷。

状态转移

下面需要分情况来进行状态转移：

1. $j=0$，此时由于$i+1$位置不是雷，$s[i]$只能是01?。如果$s[i]=$0，那$i-1$位置就不可能是雷，状态转移方程为$f[i][j]=f[i-1][0]$；如果$s[i]=$1，那$i-1$位置就必须是雷，状态转移方程为$f[i][j]=f[i-1][1]$；否则因为$i$位置不能是雷，$i-1$位置的状态不能是$2$，但是可能是$0$或$1$，状态转移方程为$f[i][j]=f[i-1][0]+f[i-1][1]$。
2. $j=1$，此时如果$s[i]=$*，那就直接有$f[i][j]=f[i-1][2]$；如果$s[i]=$?，那就让当前位置为*，仍然有$f[i][j]=f[i-1][2]$。
3. $j=2$，此时由于$i+1$位置是雷，$i$位置只不可能是$0$。如果$s[i]=$1，那么由于$i+1$位置已经是雷了，$i-1$位置不可能是雷，状态转移方程为$f[i][j]=f[i-1][0]$；如果$s[i]=$2，那就还缺一个雷，$i-1$位置必须是雷，状态转移方程为$f[i][j]=f[i-1][1]$；如果$s[i]=$*，状态转移方程为$f[i][j]=f[i-1][2]$；最后一种情况$s[i]=$?，都有可能，如果当前位置是雷，$i-1$的$j=2$，否则既有可能是$0$，也有可能是$1$，状态转移方程为$f[i][j]=f[i-1][0]+f[i-1][1]+f[i-1][2]$。

当$i=0$时到达边界，$i$位置是不可能是雷的，因此只有在$j=0$或$2$时能生成一种合法方案。用记忆化搜索从$n$推到$0$来实现这个动态规划即可，而$n+1$位置什么都没有，所以$n$位置的$j$不能等于$2$，答案应该是$f[n][0]+f[n][1]$。

复杂度分析

时间复杂度

状态的数量是$n \times 3$的量级，单次状态转移的时间复杂度是$O(1)$，因此整个算法的时间复杂度为$O(n)$。

空间复杂度

空间瓶颈在于DP数组$f$，它的规模是$n \times 3$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000010, MOD = 1e9 + 7;
char s[N];
int f[N][3];

int dfs(int i, int j) {
    if(i == 0) {
        return j != 1? 1: 0;
    }
    int &v = f[i][j];
    if(v != -1) return v;
    int cnt = 0;
    if(j == 0) {
        // i位置不能是雷
        if(s[i] == '0') {
            cnt = dfs(i - 1, 0);     // s[i+1]不是雷，i-1必然也不是雷
        }else if(s[i] == '1') {
            cnt = dfs(i - 1, 1);     // s[i+1]不是雷，i-1必须是雷
        }else if(s[i] == '?') {
            cnt = (dfs(i - 1, 0) + dfs(i - 1, 1)) % MOD;
        }
    }else if(j == 1) {
        // i位置一定是雷
        if(s[i] == '*' || s[i] == '?') {
            cnt = (cnt + dfs(i - 1, 2)) % MOD;
        }
    }else {
        // i+1位置是雷
        if(s[i] == '1') {
            cnt = dfs(i - 1, 0);
        }else if(s[i] == '2') {
            cnt = dfs(i - 1, 1);
        }else if(s[i] == '*') {
            cnt = dfs(i - 1, 2);
        }else if(s[i] == '?') {
            cnt = ((dfs(i - 1, 0) + dfs(i - 1, 1)) % MOD + dfs(i - 1, 2)) % MOD;
        }
    }
    return v = cnt;
}

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    memset(f, -1, sizeof(f));
    int res1 = dfs(n, 0);
    memset(f, -1, sizeof(f));
    int res2 = dfs(n, 1);
    printf("%d\n", (res1 + res2) % MOD);
    return 0;
}