Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ1426 收集邮票

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<bits/stdc++.h>
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;
}

本文链接:http://www.mayflyyh.com/archives/256
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      BZOJ1426 收集邮票
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ1426 收集邮票
1426: 收集邮票 Time Limit: 1 Sec Memory Limit: 162 MB Description 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一…
扫描二维码继续阅读
2018-07-12