首页 > 代码库 > Uva 10081 Tight words (概率DP)
Uva 10081 Tight words (概率DP)
Time limit: 3.000 seconds
Given is an alphabet {0, 1, ... , k}, 0 <= k <= 9 . We say that a word of length n over this alphabet is tightif any two neighbour digits in the word do not differ by more than 1.
Input is a sequence of lines, each line contains two integer numbers k and n, 1 <= n <= 100. For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, ... , k} with 5 fractional digits.
Sample input
4 1 2 5 3 5 8 7
Output for the sample input
100.00000 40.74074 17.38281 0.10130
题意:给定两个数k,n。用 {0, 1, ... , k}的数组成一个n个数的序列,如果这个序
列每两个相邻的数相差<=1,就记为是tight,求这种序列占总序列的比率。
思路: dp[i][j]表示第i为数字是j的概率 。
即 dp[i][j] = 1/(k+1) * (dp[i-1][j-1]+dp[i-1][j] + dp[i+1][j] );
注意下边界就OK了。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn=105; double dp[maxn][15],t,ans; int n,k; void initial() { memset(dp,0,sizeof(dp)); t=1.0/(k+1),ans=0.0; for(int j=0; j<=k; j++) dp[1][j]=t; } void solve() { for(int i=2; i<=n; i++) for(int j=0; j<=k; j++) { dp[i][j]+=t*dp[i-1][j]; if(j!=0) dp[i][j]+=t*dp[i-1][j-1]; if(j!=k) dp[i][j]+=t*dp[i-1][j+1]; } for(int j=0; j<=k; j++) ans+=dp[n][j]; printf("%.5lf\n",ans*100); } int main() { while(scanf("%d %d",&k,&n)!=EOF) { initial(); solve(); } return 0; }
Uva 10081 Tight words (概率DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。