P4550 收集邮票 [期望dp]

P4550收集邮票

题目描述

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

Solution

设 $F\left[i\right]$F[i]表示当前持有 $i$i种邮票, 还需要买 $F\left[i\right]$F[i]次得到N种邮票 则
$F\left[i\right]=\frac{i}{N}\left(F\right[i]+1)+\frac{N-i}{N}\left(F\right[i+1]+1)$F[i]=Ni​(F[i]+1)+NN−i​(F[i+1]+1)
化简得
$F\left[i\right]=F[i+1]+\frac{N}{N-i}$F[i]=F[i+1]+N−iN​

考虑使用当前的结果对后面增加的花费列方程, 得到下式.

设 $G\left[i\right]$G[i]表示当前持有 $i$i种邮票, 还需要买 $G\left[i\right]$G[i]块钱得到N种邮票则
$G\left[i\right]=\frac{i}{N}\left(G\right[i]+F[i]+1)+\frac{N-i}{N}\left(G\right[i+1]+F[i+1]+1)$G[i]=Ni​(G[i]+F[i]+1)+NN−i​(G[i+1]+F[i+1]+1)
化简得
$G\left[i\right]=\frac{i}{N-i}F\left[i\right]+G[i+1]+F[i+1]+\frac{N}{N-i}$G[i]=N−ii​F[i]+G[i+1]+F[i+1]+N−iN​

注: 还有类似上方, 站在整体角度, 考虑当前结果对后方影响列方程的题目, 这里 .

Code

#include<bits/stdc++.h>

double F[10005], G[10005];

int main(){
        int N;
        scanf("%d", &N);
        F[N] = 0, G[N] = 0;
        for(int i = N-1; i >= 0; i --) F[i] = N*1.0/(N*1.0-i) + F[i+1];
        for(int i = N-1; i >= 0; i --) G[i] = i*1.0/(N*1.0-i)*F[i] + G[i+1] + F[i+1] + N*1.0/(N*1.0-i);
        printf("%.2lf\n", G[0]);
        return 0;
}