有一个 1 维的扫雷游戏，每个格子用表示有雷，用 0/1/2 表示无 雷并且相邻格子中有 0/1/2 个雷。 给定一个仅包含?、、0、1、2 的字符串 s，问有多少种方法将所 有的?改为*/0/1/2 使其合法。
dp题，思路不复杂，但是状态比较多
有一点类似于状压定义的方式，dp[i][j]，表示i位置是j符号
dp[][0]->0 dp[][2]->2 dp[][3]->1 左有炸弹 dp[][4]->1右有炸弹 dp[][1]自己是炸弹
转移就是挨着推
0：i-1位置周围无炸弹，或i-1左边有炸弹
1：i-1位置周围是两个炸弹，或i-1右边有炸弹，或i-1也是炸弹
2：i-1必须自己是炸弹
3：i-1必须是炸弹
4：i-1位置周围无炸弹，或i-1左有炸弹
需要注意的是，起点的周围不能有两个炸弹，起点的左边不能有炸弹。终点的周围不能有两个炸弹，终点的右边不能有炸弹。
#include<bits/stdc++.h> using namespace std; #define N 1001000 #define mod 1000000007 #define ll long long ll n,ans,dp[N][5]; char s[N]; int main() { scanf("%s",s+1);n=strlen(s+1); if(s[1]==‘0‘)dp[1][0]=1; if(s[1]==‘1‘)dp[1][4]=1; if(s[1]==‘*‘)dp[1][1]=1; if(s[1]==‘?‘)dp[1][0]=1,dp[1][1]=1,dp[1][4]=1; for(ll i=2;i<=n;i++) { if(s[i]==‘?‘) { dp[i][0]=(dp[i-1][3]+dp[i-1][0])%mod; dp[i][1]=(dp[i-1][2]+dp[i-1][4]+dp[i-1][1])%mod; if(i!=n)dp[i][2]=dp[i-1][1]; dp[i][3]=dp[i-1][1]; if(i!=n)dp[i][4]=(dp[i-1][0]+dp[i-1][3])%mod; } else { if(s[i]==‘*‘)dp[i][1]=(dp[i-1][2]+dp[i-1][4]+dp[i-1][1])%mod; if(s[i]==‘0‘)dp[i][0]=(dp[i-1][3]+dp[i-1][0])%mod; if(s[i]==‘1‘) { dp[i][3]=dp[i-1][1]; dp[i][4]=(dp[i-1][0]+dp[i-1][3])%mod; } if(s[i]==‘2‘)dp[i][2]=dp[i-1][1]; } } ans=(dp[n][0]+dp[n][1]+dp[n][3])%mod; printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/NSD-email0820/p/9550173.html