题目大意:给定一个栈,向栈里连续添加n次,每次可以添加U或者L,如果出现连续三个U则为不安全,问有多少种不安全的可能。
解题思路:先求出安全的,用总数减去安全的即为答案。
dp[i][j]表示以第i个位置结尾时,有末尾有j个连续的U。
还有一种解法,dp[i]表示第i个位置以L结尾的总数,dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
解法一:
#include <cstdio>
#include <cstring>
typedef long long ll;
ll dp[40][3];
ll solve (int n) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++)
dp[i][0] += dp[i-1][j];
for (int j = 1; j <= 2; j++)
dp[i][j] = dp[i-1][j-1];
}
ll ans = 0;
for (int i = 0; i < 3; i++)
ans += dp[n][i];
return (1LL<<n)-ans;
}
int main () {
int n;
while (scanf("%d", &n) == 1 && n) {
printf("%lld\n", solve(n));
}
return 0;
}
解法二:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[40];
ll solve(int n) {
memset(dp, 0, sizeof(dp));
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= min(3, i); j++)
dp[i] += dp[i-j];
}
ll ans = 0;
for (int i = 0; i <= min(n, 2); i++)
ans += dp[n-i];
return (1LL<<n)-ans;
}
int main () {
int n;
while (scanf("%d", &n) == 1 && n) {
printf("%lld\n", solve(n));
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC