【题解】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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>

using namespace std;
const int N = 10005;
double n, k;
double f[N], g[N];

int main() {
cin >> n;
for (int i = n - 1; i >= 0; i--) {
f[i] = f[i + 1] + n / (double) (n - (double) i);
g[i] = f[i] * (double) i / (n - (double) i) + g[i + 1] + f[i + 1] + n / (double) (n - (double) i);
}
printf("%.2lf", g[0]);
return 0;
}