首页 > 代码库 > UVA10081 - Tight Words(dp)
UVA10081 - Tight Words(dp)
UVA10081 - Tight Words(dp)
题目链接
题目大意:给你数字【0..k],然后要求你找出这样的序列,长度为n,并且相邻的两个数字之间的相差不能超过1.问这样的数字序列出现的概率。
解题思路:之前一直反着想这题,一心想找出相邻的的数字相差大于1的,结果发现这题还是要正着想才好写。。。还有一个问题,之前没有想到直接计算概率,而是想着统计总共有多少种,然后除以总数。结果发现9^100,好大,还差点想用大数了。。。记忆化搜索,dp[n][num]:已经排到第n个数,而且第n个数是num,那么下个数就是num,或者num - 1, 或者num + 1,如果符合【1..k]的话。
代码:
#include <cstdio>
#include <cstring>
const int maxn = 105;
const int maxm = 10;
int K, N;
double p[maxn][maxm];
void init () {
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxm; j++)
p[i][j] = -1.0;
}
double dp(int n, int k) {
double& ans = p[n][k];
if (ans != -1)
return ans;
if (n == N)
return ans = 1.0;
ans = dp(n + 1, k);
if (k - 1 >= 0)
ans += dp(n + 1, k - 1);
if (k + 1 <= K)
ans += dp(n + 1, k + 1);
ans *= 1.0/(K + 1);
return ans;
}
int main () {
while (scanf ("%d%d", &K, &N) != EOF) {
init();
double ans = 0;
for (int i = 0; i <= K; i++)
ans += dp(1, i);
printf ("%.5lf\n", ans * 100.0/(K + 1));
}
return 0;
}
UVA10081 - Tight Words(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。