【题解】P4550 收集邮票
题目大意
有\(n(n\le 10000)\)种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是购买,每次只能买一张,并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的,概率均为\(\frac{1}{n}\)。购买第\(k\)次邮票需要支付\(k\)元钱。
求得到所有种类的邮票需要花费的钱数目的期望。
分析
这是一道期望题,想到用期望\(\text{dp}\)解决。
期望\(\text{dp}\)的定义状态一般都为已经完成一部分,还需要完成的期望。
用\(f_i\)表示现在取到\(i\)种邮票,要取完剩下邮票的期望次数。所以下一次取有\(\frac{i}{n}\)的概率取到已经有的,期望为\(\frac{i}{n}\times f_i\);有\(\frac{n-i}{n}\)的概率取到没有的,期望为\(\frac{n-i}{n} \times f_{i+1}\),这次取邮票的期望值为\(1\)。
所以,总期望为: \[ f_i=\frac{i}{n}\times f_i+\frac{n-i}{n}\times f_{i+1}+1 \] 化简一下: \[ f_i=f_{i+1}+\frac{n}{n-i} \] 再设一个\(g_i\),表示现在取到\(i\)张邮票,要取完剩下邮票的期望价格。所以下一次取有\(\frac{i}{n}\)的概率取到已经有的,期望为\(\frac{i}{n}\times (g_i+f_i+1)\);有\(\frac{n-i}{n}\)的概率取到没有的,期望为\(\frac{n-i}{n} \times (f_{i+1}+g_{i+1}+1)\)
化简后可得总期望: \[ g_i=\frac{i}{n-i}\times f_i+g_{i+1}+f_{i+1}+\frac{n}{n-i} \]
实现
附完整代码\((41ms,740.00kb)\)
1 |
|