Codeforces Round #237 (Div. 2)(D)

这场比赛比得非常搓，cf已经连跌7场了，从紫变绿，算是很少见的了吧，在这几场跌分的比赛中我一直在反思为什么老是这样，今天把头发剪短了些，让自己换一种状态做题，提醒自己必须要注意的一点，做一道题，先想清楚了再写。赛后苦逼地补了D题，最近做DP感觉自己智商实在不行，花了比较长的时间，智商实在是不行。小小总结一下这个比较常见的题型

D

方法一:（我的做法）

dp[i][j]

j = 0 表示i行为0

j = 1表示i行为1,i-1行不为雷

j = 2表示i行为1,i-1行为雷

j = 3表示i行为2

j = 4表示i行为雷

状态转移见代码1

方法二：

dp[i][j]

j＝0表示i 行i+1行都为数字

j＝1表示i 行为数字，i+1行为雷

j＝2表示i行为雷，i+1行为数字

j＝3表示i行i+1行都为雷

状态转移见代码2

代码1:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000006;
const int mod = 1e9+7;
int dp[N][5];
char s[N];
int n;
void add(int &x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}
int main(){
	int i, j;
	scanf("%s", s+1);
	n = strlen(s+1);
	dp[0][0] = dp[0][1] = 1;
	for(i = 1; i <= n; i++) {
		bool g = (s[i] == ‘?‘);
		if(g || s[i]==‘0‘) {
			add(dp[i][0], dp[i-1][0]);
			add(dp[i][0], dp[i-1][2]);
		}
		if(g || s[i] == ‘1‘) {
			add(dp[i][1], dp[i-1][0]);
			add(dp[i][1], dp[i-1][2]);
			add(dp[i][2], dp[i-1][4]);
		}
		if(g || s[i] == ‘2‘) {
			add(dp[i][3], dp[i-1][4]);
		}
		if(g || s[i] == ‘*‘) {
			add(dp[i][4], dp[i-1][4]);
			add(dp[i][4], dp[i-1][1]);
			add(dp[i][4], dp[i-1][3]);
		}
	}
	int ans = 0;
	bool g = (s[n] == ‘?‘);
	if(g || s[n] == ‘0‘) {
		add(ans, dp[n][0]);
	}
	if(g || s[n] == ‘1‘) {
		add(ans, dp[n][2]);
	}
	if(g || s[n] == ‘2‘) {
		add(ans, 0);
	}
	if(g || s[n] == ‘*‘) {
		add(ans, dp[n][4]);
	}
	printf("%d\n", ans);
	return 0;
}

代码二：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000006;
const int mod = 1e9+7;
int dp[N][6];
char s[N];
int n;
void add(int &x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}
int main() {
	int i, j;
	scanf("%s", s+1);
	n = strlen(s+1);
	dp[0][0] = dp[0][1] = 1;
	for(i = 1; i <= n; i++) {
		int g = (s[i] == ‘?‘);
		if(g || s[i] == ‘0‘) {
			add(dp[i][0], dp[i-1][0]);
		}
		if(g || s[i] == ‘1‘) {
			add(dp[i][1], dp[i-1][0]);
			add(dp[i][0], dp[i-1][2]);
		}
		if(g || s[i] == ‘2‘) {
			add(dp[i][1], dp[i-1][2]);
		}
		if(g || s[i] == ‘*‘) {
			add(dp[i][3], dp[i-1][3]);
			add(dp[i][3], dp[i-1][1]);
			add(dp[i][2], dp[i-1][3]);
			add(dp[i][2], dp[i-1][1]);
		}
	}
	bool g = (s[n] == ‘?‘);
	int ans = 0;
	if(g || s[n] == ‘2‘)
		add(ans, 0);
	if(g || s[n] == ‘0‘ || s[n] == ‘1‘)
		add(ans, dp[n][0]);
	if(g || s[n] == ‘*‘)
		add(ans, dp[n][2]);
		printf("%d\n", ans);
	return 0;
} 

Codeforces Round #237 (Div. 2)(D),布布扣,bubuko.com

Codeforces Round #237 (Div. 2)(D)

原文：http://blog.csdn.net/auto_ac/article/details/21648247