首页 > 代码库 > UVA 580 - Critical Mass(DP)

UVA 580 - Critical Mass(DP)

题目链接:580 - Critical Mass

题意:一个栈,里面可以放L和U,有三个连续的U就是不安全的,问共有几种不安全的情况
思路:dp,dp[i][j][k],表示放到第i个,最后两个状态为j,k表示有没有出现不安全。然后去记忆化搜索一下就可以了
然后还有一种做法是,先考虑安全的情况,在用总情况(1<<n 种)减去安全的情况,安全的情况的递推方式很容易dp[i]表示放第i个, dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
不过这题都没给数据范围,不过数据其实并不大,不然计算的时候种数一下就会超过范围了
代码:
#include <stdio.h>
#include <string.h>

int n, dp[32][4][2];

int dfs(int num, int s, int flag) {
	int &ans = dp[num][s][flag];
	if (ans != -1) return ans;
	ans = 0;
	if (num == n) {
		if (flag) ans = 1;
		return ans;
	}
	int ss = ((s&1)<<1);
	if (flag == 1)	
		ans = dfs(num + 1, ss|1 , 1) + dfs(num + 1, ss, 1);
	else
		ans = dfs(num + 1, ss|1, s == 3) + dfs(num + 1, ss, 0);
	return ans;
}

int main() {
	while (~scanf("%d", &n) && n) {
		memset(dp, -1, sizeof(dp));
		printf("%d\n", dfs(0, 0, 0));
	}
	return 0;
}