题干:

相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了
,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字
表示和它8连通的格子里面雷的数目。现在棋盘是n×2的,第一列里面某些格子是雷,而第二列没有雷,如下图: 
由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放
方案。

Input

  第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000)

Output

  一个数,即第一列中雷的摆放方案数。

Sample Input

2 1 1

Sample Output

2

Hint

解题报告:

    简单但是十分不错的dp题。

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 10000 + 5;
ll dp[MAX][2][2];//dp[i][j][k]截止第i行,这一行为j,上一行为k。 
int a[MAX]; 
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
//	if(a[1] != 0) {
		dp[1][1][0]=dp[1][1][1]=dp[1][0][0]=dp[1][0][1]=1;
//	}
//	dp[1][0][0] = dp[1][1][0]=1;
	//dp[][这行][上行]   dp[i行][i行][i-1行]
	for(int i = 2; i<=n+1; i++) {
		if(a[i-1] == 1) {
			dp[i][1][0] += dp[i-1][0][0];
			dp[i][0][0] += dp[i-1][0][1];
			dp[i][0][1] += dp[i-1][1][0];
			//默认其余的为0.。 
		}
		if(a[i-1] == 0) {
			dp[i][0][0] += dp[i-1][0][0];
		}
		if(a[i-1] == 2) {
			dp[i][1][0] += dp[i-1][0][1];
			dp[i][1][1] += dp[i-1][1][0];
			dp[i][0][1] += dp[i-1][1][1];
		}
		if(a[i-1] == 3) {
			dp[i][1][1] += dp[i-1][1][1];
		}
	}
	ll ans = 0;
	ans = /*dp[n+1][1][0] + dp[n+1][1][1] +*/ dp[n+1][0][0] + dp[n+1][0][1];
	printf("%lld\n",ans);
	return 0 ;
 }

总结:

注意合法状态和不更新状态的区别!!!有的是非法状态(此题中就要是0而不是INF,因为表示的是方法数),有的是不更新状态(此题中也是0,但是是无法到达状态,而不是非法状态),也就是,都是0但是含义不同!!

之所以更新成1,也是因为方法数是1。(只选这一种方法,所以方法数是1啊)

其实这个代码是不对的(虽然也AC了),初始化状态的时候应该用下面那个注释掉的,因为不然的话输入1 1就会错。,。。

注意不能输出dp[n][][]的四个状态的和!!!因为那样就不一定满足第n行的性质了!!!所以一定要让状态转移结束以后再找结果!!不能直接输出第n行的四个状态的和。

附一种解法:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
ll n,x,y,c;
const int MAX = 10000 + 5;
ll dp[MAX][2][2];//dp[i][j][k]截止第i行,这一行为j,上一行为k。
int a[MAX];
int main() {
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	dp[1][0][0] = dp[1][1][0]=1;
	//dp[][这行][上行]   dp[i行][i行][i-1行]
	for(int i = 2; i<=n+1; i++)
		for(int las = 0 ; las <= 1 ; las++)
			for(int llas = 0; llas<=1; llas++)
				for(int now = 0; now<=1; now++)
					if(las+llas+now == a[i-1])
						dp[i][now][las] += dp[i-1][las][llas] ;
	ll ans = dp[n+1][0][0] + dp[n+1][0][1];
	printf("%lld\n",ans);
	return 0 ;
}

或者:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
ll n,x,y,c;
const int MAX = 10000 + 5;
ll dp[MAX][2][2];//dp[i][j][k]截止第i行,这一行为j,上一行为k。
int a[MAX];
int main() {
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	dp[0][0][0] = dp[0][1][0]=1;
	//dp[][下一行][这一行行]   dp[i行][i+1行][i行]
	for(int i = 1; i<=n; i++)
		for(int las = 0 ; las <= 1 ; las++)
			for(int llas = 0; llas<=1; llas++)
				for(int now = 0; now<=1; now++)
					if(las+llas+now == a[i])
						dp[i][now][las] += dp[i-1][las][llas] ;
	ll ans = dp[n][0][0] + dp[n][0][1];
	printf("%lld\n",ans);
	return 0 ;
}