BZOJ1426 收集邮票

作者: MayFlyyh 分类: DP, 期望 发布时间: 2018-07-12 15:55 ė 6 没有评论

> 1426: 收集邮票

> Time Limit: 1 Sec Memory Limit: 162 MB

> Description

> 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且
买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k
张邮票需要支付k元钱。现在皮皮手中没有邮票,皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

> Input
一行,一个数字N N<=10000 > Output 要付出多少钱. 保留二位小数

> Sample Input 3
> Sample Output 21.25

设F[i]为当前有i种,期望购买F[i]张能买n种

所以F[n]=0

F[i]=F[i]*(i/n)+F[i+1]*(n-i)/n

设G[i]为当前买了i种,期望用G[i]元买够n种,G[n]=0

G[i]=(G[i]+F[i]+1)*(i/n)+(F[i+1]+G[i+1]+1)*(n-i)/n;

因为第k张为k元。。我们却要倒推,所以当做第n张为1元,第1张为n元

G[i+1]为买i+2~n时期望的价格 F[i+1]+1为买第i张期望的价格

“`
#include
const int N = 10100;
double F[N],G[N];
int n;
int main (){
scanf(“%d”,&n);
F[n]=0;G[n]=0;
for(int i=n-1;i>=0;–i)
F[i]=(F[i+1])+n*1.0/(n-i);
for(int i=n-1;i>=0;–i){
G[i]=(i*1.0/(n-i))*F[i]+G[i+1]+F[i+1]+n*1.0/(n-i);
}
printf(“%.2lf”,G[0]);
return 0;
}

“`

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/256

发表评论

电子邮件地址不会被公开。

Ɣ回顶部