首页 > 代码库 > 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)