BZOJ1426:收集邮票 期望dp
思路:
網上的倒着推的題解看不懂QAQ.我偏要正着推!
令\(f_i\)表示得到\(i\)種不同的郵票時的期望購買次數,\(g_i\)表示得到\(i\)種不同的郵票時的期望代價.
考慮\(f_i\),我們有:
\[f_i=f_{i-1}+\frac{1}{\frac{n-i+1}{n}}\]
這是因爲若一件事件發生的概率爲\(p\),那麼期望經過\(\frac{1}{p}\)次事件纔會發生這個事件.
接下來是\(g_i\):
\[\small{g_i=g_{i-1}+(f_{i-1}+1)*\frac{n-i+1}{n}+(f_{i-1}+1+f_{i-1}+2)*\frac{i-1}{n}*\frac{n-i+1}{n}+...}\]
总之我们计算出每种购买邮票数目的情况的概率即可.
接下来还要用等比数列公式计算极限.经过一番艰辛的计算(这里省略),我们得到:
\[g_i=f_{i-1}*\frac{n}{n-i+1}+(\frac{n}{n-i+1})^2\]
那么我们就可以在\(O(n)\)的时间里解决这道题目了.
(这样的好处就是不用开数组,内存\(O(1)\))~~~
#include<cstdio>
int main(){double f=1,ff,g=1,t;int n;scanf("%d",&n);fclose(stdin);for(int i=2;i<=n;++i)t=(double)n/(n-i+1),ff=f+t,g=g+(f+t)*t,f=ff;printf("%.2lf",g);}
评论 (0)