UVa 10081 Tight Words （DP）

UVa 10081 Tight Words （DP）2014-07-25

10081 - Tight Words

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1022

思路：长度为i的串，如果其末尾数是j，那么这样的串的个数必为长为i-1的串的，尾数为j-1,j,j+1三种情况的数目之和（在边界范围内）

完整代码：

/*0.019s*/#include<bits/stdc++.h>using namespace std;double dp[111][11];int main（）{int k, n, i, j;double ans;while （~scanf（"%d%d", &k, &n））{for （i = 0; i <= k; ++i）dp[1][i] = 1.0 / （k + 1）;for （i = 2; i <= n; ++i）for （j = 0; j <= k; ++j）{dp[i][j] = dp[i - 1][j] / （k + 1）;if （j > 0） dp[i][j] += dp[i - 1][j - 1] / （k + 1）;if （j < k） dp[i][j] += dp[i - 1][j + 1] / （k + 1）;}ans = 0;for （i = 0; i <= k; i++） ans += dp[n][i];printf（"%.5f
", ans * 100）;}return 0;}

作者：csdn博客 synapse7