首页 > 代码库 > uva 12730(期望经典)
uva 12730(期望经典)
选自： http://blog.csdn.net/myhelperisme/article/details/39724515
用dp(n)表示有n个位置时的期望值，那么，对于一个刚进来的人来说，他有 n 个选择，当他选择第 i 个位置时，此时的期望值是 [dp(i-k-1) + dp(n-i-k) + 1] / n, 推导一下，就得 (2 * sum(n-k-1) ) / i + 1, （sum(i)是指 有1～n个位置时的dp总和。
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <stdlib.h>using namespace std;#define N 1001000double f[N];int main(){ int n,k; int T; int tt=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1;i<=k+1;i++) f[i]=1; double sum=f[1]; for(int i=k+2;i<=n;i++) { f[i]=1+sum*2.0/(double)i; sum+=f[i-k]; } printf("Case #%d: ",tt++); printf("%lf\n",f[n]); } return 0;}
uva 12730(期望经典)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。