[CSP-S模拟测试]:mine（DP）

题目描述

有一个$1$维的扫雷游戏，每个格子用$*$表示有雷，用$0/1/2$表示无雷并且相邻格子中有$0/1/2$个雷。
给定一个仅包含$?$、$*$、$0$、$1$、$2$的字符串$s$，问有多少种方法将所有的$?$改为$*/0/1/2$使其合法。

输入格式

一行一个字符$s$。

输出格式

一行一个整数表示答案，对${10}^9+7$取模。

样例

样例输入：

?1?

样例输出：

数据范围与提示

对于$30\%$的数据，$|S|\leqslant 20$。
对于$60\%$的数据，$|S|\leqslant 1,000$。
对于$100\%$的数据，$|S|\leqslant {10}^6$。

题解

显然数据范围只允许我们$\Theta(n)$求解，那么也只能考虑$DP$了。

设$dp[i][j]$表示到了$i$位置，当前选了$j$，$j$分为五种情况，如下：

　　$\alpha.$当前位置没有雷。

　　$\beta.$当前位置左边有一个雷。

　　$\gamma.$当前位置旁边有两个雷。

　　$\delta.$当前位置有雷。

　　$\epsilon.$当前位置左边有雷。

为方便，以上五种情况下面均以数字$0\sim 5$代替。

那么现在来考虑转移，首先是第一个位置，分为四种情况：

　　$\alpha.$无雷：$dp[1][0]=1$。

　　$\beta.$旁边有一个雷：$dp[1][4]=1$。

　　$\gamma.$本身有雷：$dp[1][3]=1$.

　　$\delta.$为$?$：$dp[1][0]=dp[1][3]=dp[1][4]=1$（第一个位置不可能出现$1,2$两种情况）。

那么我们在来考虑过程中的转移，依然分类讨论（注意以下''中为题目中给出的棋盘的状态，而不是我上面列出的对于五种情况的编号）：

　　$\alpha.'0':$可以由$0,1$两种情况转移得来，即为：$dp[i][0]=dp[i-1][0]+dp[i-1][1]$。

　　$\beta.'1':$则还分两种情况，分别是$1$和$4$，那么式子为：$dp[i][1]=dp[i-1][3]$和$dp[i][4]=dp[i-1][0]+dp[i-1][1]$。

　　$\gamma.'2':$只能由$3$转移得来，即：$dp[i][2]=dp[i-1][3]$。

　　$\delta.'*':$可以由$2,3,4$三种情况转移得来，即：$dp[i][3]=dp[i-1][2]+dp[i-1][3]+dp[i-1][4]$。

　　$\epsilon.'?'$包含以上所有情况。

最后来考虑如何统计答案，因为最后一位不可能是$2$和$4$两种情况，所以答案即为：$dp[n][0]+dp[n][1]+dp[n][3]$。

时间复杂度：$\Theta(n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

char ch[1000001];

long long dp[1000001][5];

int main()

{

	scanf("%s",ch+1);

	int n=strlen(ch+1);

	switch(ch[1])

	{

		case '0':dp[1][0]=1;break;

		case '1':dp[1][4]=1;break;

		case '*':dp[1][3]=1;break;

		case '?':dp[1][0]=dp[1][4]=dp[1][3]=1;break;

	}

	for(int i=2;i<=n;i++)

		switch(ch[i])

		{

			case '0':dp[i][0]=(dp[i-1][0]+dp[i-1][1])%1000000007;break;

			case '1':dp[i][1]=dp[i-1][3];dp[i][4]=(dp[i-1][0]+dp[i-1][1])%1000000007;break;

			case '2':dp[i][2]=dp[i-1][3];break;

			case '*':dp[i][3]=(dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%1000000007;break;

			case '?':

				dp[i][0]=(dp[i-1][0]+dp[i-1][1])%1000000007;

				dp[i][1]=dp[i-1][3];

				dp[i][3]=(dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%1000000007;

				dp[i][4]=(dp[i-1][0]+dp[i-1][1])%1000000007;

				dp[i][2]=dp[i-1][3];

			break;

		}

	printf("%lld",(dp[n][0]+dp[n][1]+dp[n][3])%1000000007);

	return 0;

}

rp++

巴特西