P4550-收集邮票

题目:

题目描述:

有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

输入格式:

一行,一个数字N
N<=10000

输出格式:

要付出多少钱.
保留二位小数

样例:

样例输入1:

1

3

样例输出1:

1

21.25

思路:

概率题是真的仙

用$f[i]$表示现在取到$i$张邮票,要取完剩下邮票的期望次数 显然$f[n]=0$ 现在已经取得$i$张邮票,所以下一次取邮票有$\frac{i}{n}$的概率取到已经有的,期望为$\frac{i}{n}*f[i]$ 有$\frac{n-i}{n}$的概率取到没有的,期望为$\frac{n-i}{n}*f[i+1]$,这次取邮票的期望为1,所以总期望为: $$f[i]=\frac{i}{n}*f[i]+\frac{n-i}{n}*f[i+1]+1$$ 化简可得:$f[i]=f[i+1]+\frac{n}{n-i}$

用$g[i]$表示现在取到$i$张邮票,要取完剩下邮票的期望价格 显然$g[n]=0$ 现在已经取得$i$张邮票,所以下一次取邮票有$\frac{i}{n}$的概率取到已经有的,期望为$\frac{i}{n}(g[i]+f[i]+1)$,有$\frac{n-i}{n}$的概率取到没有的,期望为$\frac{n-i}{n}(g[i+1]+f[i+1]+1)$所以总期望为: $$g[i]=\frac{i}{n}(g[i]+f[i]+1)+\frac{n-i}{n}(g[i+1]+f[i+1]+1)$$ 化简可得:$g[i]=\frac{i}{n-i}*f[i]+g[i+1]+f[i+1]+\frac{n}{n-i}$

前面的推导貌似很自然的样子,但是为啥$g[i]$的推导式看着就那么奇怪呢? 那是因为式子的结构表示的是每次都将后面取到的邮票费用+1(总费用+f[i]),再加上自己的费用(+1) 这样就很好理解了

为啥不是$f[0](f[0]+1)/2n$我也想了很久 因为推导过来每次的贡献是不相同的 比如说所有情况中有1次需要取2张,1次需要取3张,那么总贡献为$(3+6)/2=4.5$,而期望次数为2.5,显然是不对的…

代码比思考简单多了

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Problem: P4550 收集邮票
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4550
// Memory Limit: 161.66 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int n;
double f[10005], g[10005];
int main()
{
    yin >> n;
    for (int i = n - 1; ~i; --i)
    {
        f[i] = f[i + 1] + (1.0 * n) / (1.0 * (n - i));
        g[i] = (1.0 * i) / (1.0 * (n - i)) * (f[i] + 1) + g[i + 1] + f[i + 1] + 1;
    }
    printf("%.2lf", g[0]);
    return 0;
}