【bzoj1426】收集邮票

2014年5月1日3,0272

Description

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

Input

一行,一个数字N N<=10000

Output

要付出多少钱. 保留二位小数

Sample Input

3

Sample Output

21.25

题解

“这种煞笔题怎么总有人问”,被吧主D了。。。

用f[i]表示已经拥有了i张邮票,则期望还需要购买的邮票数

则f[n]=0

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

整理得f[i]=f[i+1]+n/(n-i);

设g[i]为还需要的钱

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

因为可以视为这张票是1元买的,而后面的每张票都贵了1元

所以要加上f[i+1]或f[i]

然后化简得g[i]=g[i+1]+f[i+1]+((n*i)/((n-i)*n))*f[i]+(n/(n-i))

 

  • dengwxn2015年8月7日 下午10:07 回复

    请问"可以视为这张票是1元买的"这句话是什么意思?
    我知道题意说的是第i次买票要的钱是i元,怎么理解g 中这张票是1元买的?

    #1  
  • qrt2016年5月2日 上午9:36 回复

    请问究竟是怎么化简来的能不能解释一下谢谢

    #2