Description

有n种不同的邮票，每一次买一张邮票，买到每种邮票的概率都是1/n，第k次买花费k元，求买齐n种不同的邮票需要的钱的期望。

Solution

设f[i]为目前有i种不同的邮票，到买完所有邮票还需要买的邮票数的期望(倒着考虑转移方便些>.<)。

考虑本次决策，显然有f[i]=(i/n)*f[i]+((n-i)/n)*f[i+1]+1。

移项化简得到，f[i]=f[i+1]+(n/(n-i))。

由于每次的花费不同，接着考虑，设g[i]为期望的钱数。

因为到达x局面时已经有期望次数f[x]，所以本次贡献为f[x]+1。

于是有g[i]=(i/n)*(g[i]+f[i]+1)+((n-i)/n)*(g[i+1]+f[i+1]+1)。

化简得到，g[i]=(i/(n-i))*f[i]+g[i+1]+f[i+1]+n/(n-i)。

通过dp愉快地解决了本题。

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e4+5;

double f[maxn],g[maxn];
int n;

int main(){
	scanf("%d",&n);
	
	for(int i=n-1;i>=0;i--)
		f[i]=f[i+1]+n*1.0/(n-i);
		
	for(int i=n-1;i>=0;i--)
		g[i]=(i*1.0/(n-i))*f[i]+g[i+1]+f[i+1]+n*1.0/(n-i);
	
	printf("%.2lf",g[0]);
	return 0;
}