收集郵票 (概率dp)

2020 年 8 月 17 日
筆記
動規, 集訓日常

收集郵票 (概率dp)

題目描述

有 \(n\) 種不同的郵票，皮皮想收集所有種類的郵票。唯一的收集方法是到同學凡凡那裡購買，每次只能買一張，並且買到的郵票究竟是 \(n\) 種郵票中的哪一種是等概率的，概率均為 \(\frac{1}{n}\) 。但是由於凡凡也很喜歡郵票，所以皮皮購買第 \(k\) 張郵票需要支付 \(k\) 元錢。現在皮皮手中沒有郵票，皮皮想知道自己得到所有種類的郵票需要花費的錢數目的期望。

輸入格式

一行,一個數字 \(N,N\leqslant 10000\)

輸出格式

要付出多少錢. 保留二位小數

樣例

樣例輸入

樣例輸出

21.25

數據範圍與提示

\(N\leqslant 10000\)

分析

按照概率 \(dp\) 的套路，我們反向定義方程，反著推，定義 \(f[i]\) 為已經有了 \(i\) 種，還需要買幾次。 \(g[i]\) 為已經有了 \(i\) 種，還需要多少錢。

因為當前已經有了 \(i\) 種了，每種選的可能性相同，所以這一次選重複的概率為 \(\frac{i}{n}\) ，此時的次數就是 \(f[i] + 1\) ，因為當前拿了一個重複的，所以還要多拿一次，所以加一。

不重複的概率就是 \(\frac{n-i}{n}\)，次數就是 \(f[i+1] + 1\)，因為沒拿重複的，所以是拿了 \(i+1\) 種的步數加一。那麼 \(f[i]\) 的轉移就是：

\[f[i] = (f[i] + 1) \times \frac{i}{n} + (f[i+1] + 1) \times \frac{n-i}{n}
\]

化簡一下就是：

\[f[i] = f[i+1] \times \frac{n}{n-i}
\]

接下來考慮錢數的轉移，每一次增加的價格就是取的次數，而拿重複的概率是 \(\frac{i}{n}\)，所以這部分就是 \((g[i]+f[i]+1)\times \frac{i}{n}\)。

其次就是沒有重複，那麼這部分就是 \((g[i+1]+f[i+1]+1)\times \frac{n-i}{n}\)

所以總的就是 :

\[g[i] = (g[i]+f[i]+1)\times \frac{i}{n} + (g[i+1]+f[i+1]+1)\times \frac{n-i}{n}
\]

化簡完就是：

\[g[i] = \frac{i}{n-i}\times f[i] + g[i+1] + f[i+1] + \frac{n}{n-i}
\]

然後倒著枚舉，轉移就很簡單了。

程式碼

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int L = 1 << 20;
char buffer[L],*S,*T;
#define getchar() (S == T &&(T = (S = buffer) + fread(buffer,1,L,stdin),S == T) ? EOF : *S++)
const int maxn = 1e5 + 10;
double f[maxn],g[maxn];
inline int read(){
	int s = 0,f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
	int n = read();
	for(int i = n - 1; ~i ; --i){
		f[i] = f[i+1] + (1.0 * n) / (1.0 * (n - i));		
		g[i] = (1.0 * i) / (1.0 * (n - i)) * (f[i] + 1) + g[i+1] + f[i+1] + 1;
	}
	printf("%.2lf",g[0]);
	return 0;
}

Tags: 動規集訓日常