[文章目录]
Description
有n种邮票，每次买一张，对于买的这张是哪种邮票是等概率的。同时，买第i次邮票花费为i元，当n种邮票都卖到时停止。求花费钱数的期望。n<=10000
跪了。在考场上我如果死搞这道题肯定废了。
属于那种题解200行，代码20B的题。。。
设:当前已经获得x种，需要再买y次的概率。
设:已经获得x种，需要购买到n种的期望次数。
发现
再看的定义，发现:
然后尝试dp答案。
考虑新的想法，将整个次数的花费反过来，令最后一次的花费为1，然后向前递增。
令:已经获得i种，直到获得n种的期望花费。（注意，花费是从最后一次向前递增的）。
然后就推出来了。（反正别人都说是对的，我也只能跪拜了吧）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
double ans,f[11000],g[11000];
int main()
{
scanf("%d",&n);
for(int i=n-1;i>=0;i--) f[i]=f[i+1]+1.0*n/(n-i);
for(int i=n-1;i>=0;i--) g[i]=g[i+1]+f[i+1]+f[i]*i/(n-i)+1.0*n/(n-i);
printf("%.2lf",g[0]);
return 0;
}