洛谷P4550 收集邮票 题解

题目链接：P4550 收集邮票

题意：

有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。

现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

输入格式：

一行，一个数字 \(N\)（\(N \le 10000\)）。

输出格式：

输出要付出多少钱，保留二位小数。

直接求花费比较麻烦，因为不知道确切次数什么的。

俗话说，概率要顺推，期望要逆推。

考虑设 \(f_i\) 表示取了 \(i\) 种邮票，取完剩下的期望次数。显然 \(f_n = 0\) 。 \[ 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\) 种邮票，取完剩下的期望花费。显然 \(g_n = 0\) 。考虑转移。 \[ g_i = \frac{i}{n}\times(g_i + f_i + 1) + \frac{n-i}{n} \times(g_{i+1}+f_{i+1} + 1) \] 解下方程就是 \[ g_i = \frac{i}{n-i}\times f_i + g_{i+1} + f_{i+1} + \frac{n}{n-i} \] 最后答案就是 \(g_0\) ，时间复杂度 \(\mathcal{O}(n)\) 。

做完了这题，不妨思考一下，为什么期望要逆推？概率为什么又是顺推？

这题逆推的原因在于这题中初始状态是不知道的，但是结束状态是知道的，即 \(f_n = 0\) 和 \(g_n = 0\) 。

概率dp题顺推是因为一般初始状态是知道的，比如多次抛硬币，初始状态就是不扔，显然概率为 \(0\) 。

当然这个顺序也不是绝对的，要看到底是初始状态知道还是结束状态知道。

总结一下，就是 初始状态确定时可用顺推，终止状态确定时可用逆推 。

嗨害嘿，代码来咯：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4+15))

int n; double f[N],g[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=n-1; ~i; i--)
    {
        f[i] = f[i + 1] + (double)n / (n - i);
        g[i] = (double)i / (n - i) * (f[i] + 1) + g[i + 1] + f[i + 1] + 1;
    }
    cout << fixed << setprecision(2) << g[0] << '\n';
    return 0;
}

关于参考文献 [1] 提到的 \(n \times \frac{f_0 \times (f_0 + 1)}{2}\) 为什么不对，我觉得应该这么说明（参考了评论区）

设随机变量 \(x\) 为凑齐邮票所需的花费，则我们要求的是 \(E\left[\frac{1}{2}x(x+1)\right]\) ，而 \[ \mathrm{E}\left[\frac{1}{2}x(x+1)\right]\ne \frac{1}{2}\times (\mathrm{E}[x]+1)\times \mathrm{E}[x] \] 因此直接用 \(n \times \frac{f_0 \times (f_0 + 1)}{2}\) 算出来的是不对的。

---

参考文献：

[1] https://www.luogu.com.cn/blog/league/solution-p4550