洛谷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 = \frac{i}{n}\times f_i + \frac{n-i}{n} \times f_{i+1} + 1$

解下方程就是

f_{i} = f_{i + 1} + \frac{n}{n - i}

$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}\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_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$ 。

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

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

~~嗨害嘿，代码来咯~~：

cpp

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