首页 > 代码库 > UVA10081-Tight Words(递推)
UVA10081-Tight Words(递推)
题目链接
题意:给出一个0到k的序列,要求出有每相邻的两个数之间的差不差过1的子序列的概率。
思路:递推,dp[i][j]表示长度为i并且j结尾的子序列的个数。注意,如果用符合子序列个数除以从个数,数组要用double,用long long的话会爆掉。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int MAXN = 105; double dp[MAXN][MAXN]; int k, n; void init() { memset(dp, 0, sizeof(dp)); for (int i = 0; i <= k; i++) dp[1][i] = 1; for (int i = 2; i <= n; i++) for (int j = 0; j <= k; j++) { if (j == 0) dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1]; else if (j == k) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1] + dp[i - 1][j - 1]; } } int main() { while (scanf("%d%d", &k, &n) != EOF) { init(); double ans = 0; for (int i = 0; i <= k; i++) ans += dp[n][i]; double tmp = pow(k + 1, (double)n); double p = ans / tmp * 100; printf("%.5lf\n", p); } return 0; }
UVA10081-Tight Words(递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。