【期望Dp】【bzoj1426】: 收集郵票

轉自zP1nG

題目的連結

Description

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

Input

一行,一個數字N N<=10000

Output

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

Sample Input

3

Sample Output

21.25

思路

f[i]代表已經擁有了i張郵票，還需購買郵票次數的期望。顯然f[n]=0。

那麼對于已經擁有i張郵票的狀态，下一次選擇有兩種情況：

①有i/n的機率取重複的郵票，狀态依舊為f[i]，②有(n-i)/n的機率取其它的郵票，狀态進入f[i+1]

那麼我們就能得到方程f[i]=(i/n)∗f[i]+((n−i)/n)∗f[i+1]+1

整理得f[i]=f[i+1]+n/(n−i)

我們令g[i]代表已經擁有i張郵票，還需花的錢的數量。同理g[n]=0。

對于g[i]也同樣有兩種情況。已知每次取郵票花的錢比上一次多一，反過來計算，假設取第k張郵票花1元，k之前的每次比後一次多1。

那麼就有方程g[i]=((n−i)/n)∗(g[i+1]+f[i+1])+(i/n)∗(g[i]+f[i])+1

整理得g[i]=((i/n)∗f[i]+((n−i)/n)∗(g[i+1]∗f[i+1]))∗(n/(n−i))

g[0]即為所求

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
double f[],g[];
int n;
int main(){
    scanf("%d",&n);
    for(int i=n-;i>=;--i)     f[i]=f[i+]+*n/(n-i);
    for(int i=n-;i>=;--i)     g[i]=(f[i]*i/n+(g[i+]+f[i+])*(n-i)/n+)*n/(n-i);
    printf("%.2lf",g[]);   
    return ;
}