前題

$ZYCdalao$讓我推這題，然后我只推出了$f$的推導，我還是太菜了$QVQ$

---

正題

題目鏈接:https://www.luogu.org/problemnew/show/P4550

---

題目大意

$n$種，每次隨機買一個郵票(每種的概率均等)，然后第$k$種要$k$元，求收集完所有郵票需要的期望錢數。

---

解題思路

首先設$g_i$表示購買$i$個郵票，買完剩下的郵票需要的期望錢數，我們發現因為有$k$，我們很難計算答案，但我們可以將費用推后計算。先設$f_i$表示拿到了$i$個，要取完剩下的郵票需要購買的期望次數(倒推)，那么有$\frac{n?i}{n}$的概率買到正確的郵票，有$\frac{i}{n}$的概率買到之前買過的郵票
$$f_i=\frac{n?i}{n}?f_{i+1}+\frac{i}{n}?f_i+1$$
$$f_i=\frac{n?i}{n}?f_{i+1}+\frac{i}{n}?f_i+1$$
$$\frac{n?i}{n}?f_i=\frac{n?i}{n}?f_i+1$$
$$f_i=f_{i+1}+\frac{n}{n?i}$$

然后我們考慮如何推導$g_i$，我們每次有$\frac{i}{n}$的概率買到已經有了的，有$\frac{n?i}{n}$的概率買到沒有的，因為費用推后計算，所以每次后面取到的費用都會$+1$，所以現在的費用就是之前的購買次數加上原來的費用$f_i+1$，那么加上前面的購買費用就是$g_i+f_i+1$

那么推導
$$g_i=\frac{i}{n}(g_i+f_i)+\frac{n?i}{n}(g_{i+1}+f_{i+1})+1$$
$$g_i=\frac{i}{n}?g_i+\frac{i}{n}?f_i+\frac{n?i}{n}(g_{i+1}+f_{i+1})+1$$
$$\frac{n?i}{n}{g}_i=\frac{i}{n}?f_i+\frac{n?i}{n}(g_{i+1}+f_{i+1})$$
$$g_i=\frac{i}{n?i}?f_i+g_{i+1}+f_{i+1}+1$$

$over$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=11000; double n; double f[N],g[N]; int main() {scanf("%lf",&n);for(int i=n-1;i>=0;i--){f[i]=f[i+1]+(double)n/(n-i);g[i]=(double)(f[i]+1)*i/(n-i)+g[i+1]+f[i+1]+1;}printf("%.2lf",g[0]); }

總結

以上是生活随笔為你收集整理的P4550-收集邮票【期望dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。