本文主要是介绍CodeForces 404D Minesweeper 1D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一个字符串 ？可以被替换 *表示雷 数字表示旁边雷的个数 （就是扫雷游戏…） 问 这个串有几种可能的结构
思路：
画出所有转移dp就好了 画的思路就是
当前位置是什么符号 它前面是什么符号或符号组合
确定了前面的东西后 是不是也对后一位有要求（比如01后面一个必须是*）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 1000010
#define mod 1000000007int n;
char str[M];
int dp[M][4][2];int main()
{int i,j,k;scanf("%s",str+1);n=strlen(str+1);for(i=1;i<=n;i++){if(str[i]=='0'||str[i]=='?'){if(i==1) dp[i][0][0]=1;else{dp[i][0][0]=(dp[i][0][0]+dp[i-1][0][0])%mod;if( i>2 && (str[i-1]=='1'||str[i-1]=='?') && (str[i-2]=='*'||str[i-2]=='?') )dp[i][0][0]=(dp[i][0][0]+dp[i-1][1][1])%mod;}}if(str[i]=='1'||str[i]=='?'){if(i==1) dp[i][1][0]=1;else{if( i==n || (str[i-1]=='*'||str[i-1]=='?') && str[i+1]!='*' )dp[i][1][1]=(dp[i][1][1]+dp[i-1][3][0])%mod;if( i<n && (str[i-1]=='0'||str[i-1]=='?') && (str[i+1]=='*'||str[i+1]=='?') )dp[i][1][0]=(dp[i][1][0]+dp[i-1][0][0])%mod;if( i>2 && i<n && (str[i-1]=='1'||str[i-1]=='?') && (str[i-2]=='*'||str[i-2]=='?') && (str[i+1]=='*'||str[i+1]=='?') )dp[i][1][0]=(dp[i][1][0]+dp[i-1][1][1])%mod;}}if(str[i]=='2'||str[i]=='?'){if(i>1&&i<n&&(str[i-1]=='*'||str[i-1]=='?')&&(str[i+1]=='*'||str[i+1]=='?'))dp[i][2][0]=(dp[i][2][0]+dp[i-1][3][0])%mod;}if(str[i]=='*'||str[i]=='?'){if(i==1) dp[i][3][0]=1;else{if( (str[i-1]=='1'||str[i-1]=='?') && ( i==2 || str[i-2]!='*'||str[i-2]=='?' ) )dp[i][3][0]=(dp[i][3][0]+dp[i-1][1][0])%mod;if( i>2 && (str[i-1]=='2'||str[i-1]=='?') && (str[i-2]=='*'||str[i-2]=='?') )dp[i][3][0]=(dp[i][3][0]+dp[i-1][2][0])%mod;dp[i][3][0]=(dp[i][3][0]+dp[i-1][3][0])%mod;}}}printf("%d\n",(((dp[n][0][0]+dp[n][1][1])%mod+dp[n][2][0])%mod+dp[n][3][0])%mod);return 0;
}
这篇关于CodeForces 404D Minesweeper 1D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
