【2】做题心得 - 2025 NOIP #21 - T1【神人】【动态规划】

· · 题解

dp 好题。

给你一个长度为 n(n\leq 10^6) 的地图，是一个扫雷，其中 ? 不知道，求合法组数。

考虑一个线性的 dp。

我们发现一个格子的状态有 *，0，1，2，但是我们发现其中有一个 1 不是很好处理，这里我们可以把它拆分成 LEFT 和 RIGHT 表示左边有雷和右边有雷。

为了表示方便，我们接下来使用一下的表示法：

单词 含义
YES 表示 2，左右都要有雷。
NO 表示 0，左右都没有雷。
LEFT 表示 1，左边有雷。
RIGHT 表示 1，左边有雷。
ME 表示 *，自己是雷。

在 dp 时我们可以把这些状态映射到一个 0\sim 4 的维度上，就像这样：

#define NO 0     // 没有炸弹，左右也没有
#define YES 1    // 左右必须是炸弹
#define ME 2     // 本身是炸弹
#define LEFT 3   // 左边有一颗炸弹，右边没有
#define RIGHT 4  // 右边有一颗炸弹，左边没有

然后我们考虑 dp 式子怎么写。注意到我们无法简单定义 f_{0} 的状态，考虑从 f_1 开始写。

下文中由于 ? 操作本质是其他所有操作的和，所以不写。

开头状态

即 f_1，注意它不能填 2，因为没有左边的格。

0

开头为 0 是可行的，f_{1,\tt NO}=1。

1

开头为 1 是可行的，但要求右边必须为雷，f_{1,\tt RIGHT}=1。

*

开头为 * 是可行的，f_{1,\tt ME}=1。

转移状态

分五类讨论。

其中涉及 ? 的操作可能存在 i=n 而不能为 2 与 \tt RIGHT 的情况，请处理边界。

0

可以由 f_{i-1,\tt NO}，f_{i-1,\tt LEFT} 转移过来，他们满足不会在 i-1 处放雷。

\tt LEFT

当然是由 f_{i-1,\tt ME} 转移啦。

\tt RIGHT

同样可以由 f_{i-1,\tt NO}，f_{i-1,\tt LEFT} 转移过来，他们满足不会在 i-1 处放雷。

2

这个要求是 f_{i-1,\tt ME}，因为必须要有雷。

*

因为这有炸弹，所以我们考虑转移 f_{i-1,\tt RIGHT}，f_{i-1,\tt YES} 是需要这个位置有炸弹的状态。或者左边也是炸弹，反正不影响，转移 f_{i-1,\tt ME}。

统计答案

最右边可以是 f_{n,\tt ME}，f_{n,\tt LEFT} 和 f_{n,\tt NO}，求和即可。

注意取模。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define NO 0     // 没有炸弹，左右也没有
#define YES 1    // 左右必须是炸弹
#define ME 2     // 本身是炸弹
#define LEFT 3   // 左边有一颗炸弹，右边没有
#define RIGHT 4  // 右边有一颗炸弹，左边没有
const int N=1e6+10,P=1e9+7;
string s;
int n,f[N][5],ans;
int to(char ch){
    if(ch=='0')
        return NO;
    if(ch=='*')
        return ME;
    if(ch=='2')
        return YES;
    return -1;
}
signed main(){
    cin>>s;
    n=s.size();
    s=" "+s;
    s=s+" ";
    if(s[1]=='0') // 这里和左右都不能是炸弹
        f[1][NO]=1;
    if(s[1]=='1') // 开头要是 1 就只能是右是炸弹
        f[1][RIGHT]=1;
    if(s[1]=='*') // 自己是炸弹
        f[1][ME]=1;
    if(s[1]=='?') // 否则由于开头不能是 2，其他状态都标记
        f[1][NO]=1,
        f[1][ME]=1,
        f[1][RIGHT]=1;
    for(int i=2;i<=n;i++){
        if(s[i]=='*'){ // 固定炸弹
            f[i][ME]=(
                f[i-1][YES]+       // 左边要两颗炸弹
                f[i-1][RIGHT]+     // 左边要一颗炸弹
                f[i-1][ME]         // 左边也是炸弹
            )%P;
        }else if(s[i]=='0'){ // 左右都没有
            f[i][NO]=(
                f[i-1][LEFT]+      // 左边的左边有炸弹，不影响
                f[i-1][NO]         // 左边也不要炸弹
            )%P;
        }else if(s[i]=='1'){ // 左右有一颗
            f[i][LEFT]=(
                f[i-1][ME]         // 那左边一定要有炸弹
            )%P;
            f[i][RIGHT]=(          // 其实这个就是要求左边没有炸弹，跟 NO 是一样的
                f[i-1][LEFT]+      
                f[i-1][NO]
            )%P;
        }else if(s[i]=='2'){ // 左右都有
            f[i][YES]=(
                f[i-1][ME]         // 同理左边一定要有炸弹
            )%P;
        }else{ // 哪个都行
            f[i][ME]=(
                f[i-1][YES]+       // 左边要两颗炸弹
                f[i-1][RIGHT]+     // 左边要一颗炸弹
                f[i-1][ME]         // 左边也是炸弹
            )%P;        
            f[i][NO]=(
                f[i-1][LEFT]+      // 左边的左边有炸弹，不影响
                f[i-1][NO]         // 左边也不要炸弹
            )%P;    
            f[i][LEFT]=(
                f[i-1][ME]         // 那左边一定要有炸弹
            )%P;
            if(i<n) // 注意边界
                f[i][RIGHT]=(          // 其实这个就是要求左边没有炸弹，跟 NO 是一样的
                    f[i-1][LEFT]+      
                    f[i-1][NO]
                )%P;
            if(i<n) // 注意边界
                f[i][YES]=(
                    f[i-1][ME]     // 同理左边一定要有炸弹
                )%P;
        }
    }
    cout<<(
        f[n][NO]+           // 可以左边不是
        f[n][LEFT]+         // 可以左边是
        f[n][ME]            // 自己是
    )%P;
    return 0;
}