本文主要是介绍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);elseans = 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;
}这篇关于UVA 580 - Critical Mass（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
