「BZOJ1426」收集邮票

2014年5月1日5,9385

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))

 

avatar
3 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
suxxsfelindongli2004BeyondStarsqrtdengwxn Recent comment authors
  Subscribe  
提醒
suxxsfe
suxxsfe

推g[i]的式子里要用到g[i]?

qrt
qrt

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

BeyondStars

这不是自己手推一下么

dengwxn
dengwxn

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

lindongli2004
lindongli2004

假设这是 i 第一张票,需要花费 1 元,而第 i+1 张票的假设就不成立了,所以 i+1->n 这些票要贵一元。这样往复下去,即可得到 g[1] ,也就是答案。