博客

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

解法:显然这是一个概率期望题,是一个等概率事件问题,首先我们需要设出两个数组d[i]表示已经取完了i张票,取完剩下邮票的期望次数,显然d[n] = 0,我们之后需要进行逆推

对于第i次,我们有概率i / n取到已经得到过的,(n – i) / n的概率得到未得到过的邮票
那么状态转移方程未d[i] = i / n * (d[i]) + (n – i) / n * (d[i + 1]) + 1

1.化简得d[i] = d[i + 1] + n / (n – i)

之后设一个d1数组,d1[i]表示取到i张邮票,取完剩下邮票的期望价格,显然d1[n] = 0(因为取完了)
有概率i / n取到得到过的 i / n * (d[i] + d1[i] + 1)
有概率(n – i)/n取到未取到的(n – i)/n * (d[i + 1] + d1[i + 1] + 1)
得到递推方程d1[i] = i / n * (d[i] + d1[i] + 1) + (n – i)/n * (d[i + 1] + d1[i + 1] + 1)

2.化简得:d1[i] = (1.0 * i) / (1.0*(n – i)) * (d[i] + 1) + d[i + 1] + d1[i + 1] + 1

解决了!

#include<bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
const int maxn = 1e4 + 5;
double d[maxn],d1[maxn];
//d表示已经取完了i张邮票,取完剩下邮票的期望次数
//d1表示取到i张邮票,取完剩下邮票的期望价格 
int main(){
	int n;
	scanf("%d",&n);
	double ans = 0.0;
	for(int i = n - 1; i >= 0; i--){
	   d[i] = d[i + 1] + 1.0*n/(n - i);
	   d1[i] = (1.0 * i) / (1.0*(n - i))*(d[i] + 1) + d[i + 1] + d1[i + 1] + 1; 
	}
	printf("%.2lf\n",d1[0]);
	
}