bzoj1426. 收集邮票

题面

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

输入

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

输出

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

样例输入

3

样例输出

21.25

标签 bzoj1426

解答

概率与期望的题,要抓住关键期望的线性运算E(X)=ViPi。首先预处理出f数组,f[i]表示买到i张邮票的期望购买次数(不是价格),然后抓住期望就是次数这一点,f(i)=inf(i)+nin(f(i+1)+1)其中,in是购买到已经拥有的邮票的概率,乘上已经拥有的邮票的购买次数,算出购买的已经拥有的邮票的期望。nin表示已经买到表示买到不拥有的邮票的概率,乘以买到i+1张邮票的次数再加上本次购买的1。这样f就处理完了。然后考虑处理g数组,g(i)表示购买了i张邮票,还要买到n张邮票的期望价格。那么显然,g(n)=0,然后想不出来可以写出如下表达式:g(i)=in(g(i)+f(i)+1)+nin(g(i+1)+f(i+1)+1)含义是一样的,解释一下(g(i)+f(i)+1),因为已经买了i张邮票,话费了g(i)元,购买这张邮票的价格是f(i+1)+1,后面也是一样的。 代码:

# include <iostream>
# include <iomanip>
using namespace std;
const int MAXN = 10010;
double f[MAXN],g[MAXN];
int main(){
    int n;cin>>n;
    for(int i = n-1;i>=0;i--){
        f[i] = f[i+1]+double(n)/double(n-i);
        g[i] = double(i)/double(n-i)*(f[i]+1)+g[i+1]+f[i+1]+1.0;
    }
    cout.setf(ios::fixed);
    cout<<setprecision(2)<<g[0];
}