【期望DP】收集邮票

动态规划DP, 概率

传送门：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_i\times \frac{n}{n-i+1}$

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double f[1000000],g[1000000];
int main(){
	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;
}