首页 > itarticle > 【期望dp】收集邮票

【期望dp】收集邮票

admin 11月 13, 2020 0

传送门：BZOJ1426

思路：

用$f_i,g_i$分别表示收集i种邮票张数期望和花费期望；
- 可以发现：
- $f_{i-1}+1=frac{n-i+1}{n}times f_i+frac{i-1}{n}times f_{i-1}$
- $g_{i-1}+f_i=frac{n-i+1}{n}times g_i+frac{i-1}{n}times g_{i-1}$

- 整理得：
- $f_i=f_{i-1}+frac{n}{n-i+1}$
- $g_i=g_{i-1}+f_itimes frac{n}{n-i+1}$

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double f[1000000],g[1000000];
int (){
	scanf("%d",&n);
	f[0]=g[0]=0;
	for (int i=1;i<=n;i++){
		f[i]=f[i-1]+n/(n-i+1.0);
		g[i]=g[i-1]+f[i]*n/(n-i+1.0);
	}
	printf("%.2lf",g[n]);
	return 0;
}