收集郵票C++題目【概率期望DP+數學推導】

題意

Description

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

Format

Input

一行,一個數字 $n$

Output

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

Samples

輸入數據 1

輸出數據 1

21.25

$1\leq n\leq 10^4$

思路

這一道題目堪稱牛逼，需要數學功底。

設 $P (x, i)$ 表示買 $x$ 次能從 $i$ 種買到 $n$ 種的概率

設 $f_i$ 表示現在有 $i$ 張，買到 $n$ 張的期望。

那么有：
$f_i=\sum_{x=0}^\infty x\times P(x,i)\\ \begin{align} &\Leftrightarrow f_i=\frac{n-i}{n}\times f_{i +1} + \frac{i}{n}\times f_i+1\\ &\Leftrightarrow n\times f_i=(n-i)\times f_{i+1}+i\times f_i+n\\ &\Leftrightarrow (n-i)\times f_i=(n-i)\times f_{i+1}+n\\ &\Leftrightarrow f_i=f_{i+1}+\frac{n}{n-i}. \end{align}$
顯然 $f_n=0.$

考慮設 $g_{i,j}$ 表示有 $i$ 張，下一張是 $j$ 的期望。

顯然： $g_{i,j}\rightarrow g_{i,j+1}$ 的概率為 $\frac{i}{n}$ ， $g_{i,j}\rightarrow g_{i+1,j+1}$ 的概率為 $\frac{n-i}{n}$ ，并且付出代價為 $j .$

顯然有：
$g_{i,j}=\frac{i}{n}\times g_{i,j+1}+\frac{n-i}{n}\times g_{i+1,j+1}+j$
因為這是一個遞推式，不妨考慮它的性質：
$\begin{align} g_{i,j}&=&&\sum_{x=0}^\infty\left[j+(j+1)+\dots+(x+j-1) \right]\times P(x,i)\\ &=&&\sum_{x=0}^\infty\frac{x\times(x+2\times j-1)}{2}\times P(x,i)\end{align}$
考慮與 $g_{i,j+1}$ 發生聯系，做差發現：
$\begin{align}g_{i,j+1}-g_{i,j}=\sum_{x=0}^\infty\frac{x\times(x+2\times j+1 - x-2\times j+1)}{2}\times P(x,i)\\ = \sum_{x=0}^\infty \frac{x\times2}{2}\times P(x,i)= f_i\\ \therefore g_{i,j}=g_{i,j+1}-f_i. \end{align}$
化簡該式子：
$g_{i,j}=g_{i,j+1}\times \frac{i}{n}+g_{i+1,j+1}\times\frac{n-i}{n}+j\\ \begin{align} &\Leftrightarrow& g_{i,j}=(g_{i,j}+f_i)\times\frac{i}{n}+(g_{i+1,j}+f_{i+1})\times\frac{n-i}{n}+j\\ &\Leftrightarrow& n\times g_{i,j}=i\times(g_{i,j}+f_i)+(g_{i+1,j}+f_{i+1})\times(n-i)+n\times j\\ &\Leftrightarrow&n\times g_{i,j}=i\times g_{i,j}+i\times f_i+n\times g_{i+1,j}-i\times g_{i+1,j}+n\times f_{i+1}-i\times f_{i+1}+n\times j\\ &\Leftrightarrow& (n-i)\times g_{i,j}=(n-i)\times g_{i+1,j}+i\times f_i+(n-i)\times f_{i+1}+n\times j\\ &\Leftrightarrow& g_{i,j}=g_{i+1,j}+f_{i+1}+\frac{i\times f_i+n\times j}{n-i}\\ &\Leftrightarrow& g_{i,j}=g_{i+1,j}+f_{i+1}+f_i\times\frac{i}{n-i}+\frac{n\times j}{n-i} \end{align}$
顯然這里的 $j$ 對于轉移是無用的，因為我們只需要知道 $j = 1$ 的答案，所以說我們的轉移如下：
$g_{i}=g_{i+1}+f_{i+1}+f_i\times\frac{i}{n-i}+\frac{n}{n-i}$
于是我們用 $O (n + n)$ 解決了這道題目。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#define N 10005
#define ld long double
using namespace std;
int n;
ld f[N],g[N];
int main(){cin >> n;for (int i = n - 1;i >= 0;i --) f[i] = f[i + 1] + 1.0 * n / (n - i);for (int i = n - 1;i >= 0;i --) g[i] = g[i + 1] + f[i + 1] + f[i] * 1.0 * i / (n - i) + 1.0 * n / (n - i);cout << fixed << setprecision(2) << g[0];return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/10938.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/10938.shtml
英文地址，請注明出處：http://en.pswp.cn/web/10938.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！