题头

描述

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

输入

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

输出

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

样例输入

3

样例输出

21.25

一道很简单，但神需要脑量的题

本来想设数组dp [ i ]表示已经买了i种邮票的期望次数，推出了公式

如果已经有k种邮票，则多出一种的期望次数为

k/(n−k)k/(n−k)

于是得到dp的递推式

dp[i]=dp[i+1]+n/(n−i)dp[i]=dp[i+1]+n/(n−i)

但忽略了期望次数并不带表价格就是期望次数的等差数列，期望次数只是一个趋近无限时，平均次数趋近的一个值，而且次数为无限时，平均次数的值，和价格可以说没有直接关联

设g[i]表示已买了i中期望需要的钱

则

g[i]=(g[i]+dp[i]+1)∗i/n（没有买到新种类邮票）+(g[i+1]+dp[i+1]+1)∗(n−i)/i（买到新种类邮票）g[i]=(g[i]+dp[i]+1)∗i/n（没有买到新种类邮票）+(g[i+1]+dp[i+1]+1)∗(n−i)/i（买到新种类邮票）

化简就是

g[i]=g[i+1]+dp[i]∗n/(n−i)g[i]=g[i+1]+dp[i]∗n/(n−i)

答案就是

g[0]g[0]

代码

#include
    
     using namespace std;double dp[10005],g[10005];int n;int main(){    cin>>n,dp[n]=0;g[n]=0;    for(int i=n-1;i>=0;i--) dp[i]=dp[i+1]+1.0*n/(n-i),g[i]=g[i+1]+dp[i]*n/(n-i);    printf("%0.2lf",g[0]);}
    

神tm短,10行都没有，但是思路和公式很难想