【期望/概率论】收集邮票（洛谷P4550）

题目描述

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

输入

一行一个正整数n。

输出

输出期望要花费多少钱，保留两位小数。

数据范围限制

 

Solution：

题意非常简单的概率学问题，关于期望的定义详见这里

对此类问题毫无经验的我在尝试自己颓了一波放弃了

在OI这类题一般用状态转移方程解决（以下来自官方题解，很显然就不多解释了）

 

 然后O（N）倒序循环转移即可，边界条件fN=0，gN=0

另外还有的就是令人痛苦的double与int转换问题，其他没啥了

Code：

#include<bits/stdc++.h>
using namespace std;
double f[10050],g[10050];
int main()
{
    int N;
    cin>>N;
    f[N]=0;
    g[N]=0;
    double Na=1.0*N;
    for(int i=N-1;i>=0;i--){
        f[i]=f[i+1]+Na/(Na-1.0*i);
        g[i]=f[i+1]+g[i+1]+1.0*i/(Na-1.0*i)*f[i]+Na/(Na-1.0*i);
    }
    printf("%.2lf",g[0]);
    return 0;
}