【题解】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)$

#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;
}