UVa 10081 - Tight Words

传送门

题意

有一个由0~k的集合，从中选出长度为n的数字，求选出数字中相邻数字绝对值不超过1的概率。

思路

$dp[i][j]$表示长度为i的数字末尾是j的情况。

在末尾添加数字有三种情况。

是它自己。
+1
-1

\[dp[i][j] = (dp[i-1][j] + dp[i - 1][j - 1] + dp[i - 1][j + 1]) / (k + 1)\]

至于初始值，当长度为1的时候不管选什么数字都是$1 / (k + 1)$

非常巧妙的DP（๑•̀ㅂ•́)و✧

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#pragma comment(linker, "/STACK:102400000,102400000")
 
double dp[110][11];
 
int main()
{
    int k, n, i, j;
    while (~scanf("%d%d", &k, &n))
    {
        memset(dp, 0, sizeof dp);
        for (i = 0; i <= k; i++)
            dp[1][i] = 100.0 / (k + 1);
        for (i = 2; i <= n; i++)
            for (j = 0; j <= k; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j != 0)
                    dp[i][j] += dp[i - 1][j - 1];
                if (j != 9)
                    dp[i][j] += dp[i - 1][j + 1];
                dp[i][j] /= (k + 1);
            }
        double ans = 0;
        for (i = 0; i <= k; i++)
            ans += dp[n][i];
        printf("%.5f\n", ans);
    }
    return 0;
}

Published on Aug 07, 2014 in categories Posts

上一篇杂记 IV
下一篇UVa 10721 - Bar Codes