SP1026 FAVDICE - Favorite Dice[期望DP]

落日映苍穹つ 2021-11-16 08:20 210阅读 0赞

[也许更好的阅读体验][Link 1]  
\\(\\mathcal\{Description\}\\)  
一个\\(n\\)面的骰子，求期望掷几次能使得每一面都被掷到  
输入有\\(T\\)组数据，每次输入一个\\(n\\)  
输出保留两位小数

\\(\\mathcal\{Solution\}\\)  
设\\(f\[i\]\\)表示已经掷到过\\(i\\)面，**还** 期望掷多少次骰子使每一面都被掷到  
现在掷一次骰子，有两种情况

1.  有\\(\\frac\{i\}\{n\}\\)的概率掷到已经掷到过的面，此时仍然还要掷\\(f\[i\]\\)次骰子
2.  有\\(\\frac\{n-i\}\{n\}\\)的概率掷到没掷到过的面，此后就掷到过\\(i+1\\)个面了，还需掷\\(f\[i+1\]\\)次骰子

需要注意的是，无论是掷到以上哪种情况，都需要掷一次骰子  
所以有  
\\(f\[i\]=\\frac\{i\}\{n\}f\[i\]+\\frac\{n-i\}\{n\}f\[i+1\]+1\\)  
将其化简  
\\(f\[i\]=f\[i+1\]+\\frac\{n\}\{n-i\}\\)

初值\\(f\[n\]=0\\)，答案为\\(f\[0\]\\)  
应逆向循环

\\(\\mathcal\{Code\}\\)

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月21日 星期日 14时51分18秒 *******************************/ #include <cstdio> #include <fstream> using namespace std; const int maxn = 1005; //{ { {cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int T,n; double f[maxn];//f[i] -> 有了i个面，变成拥有n个面的期望 int main() { freopen("p1026.in","r",stdin); freopen("p1026.out","w",stdout); cin>>T; while (T--){ cin>>n; f[n]=0; for (int i=n-1;i>=0;--i) f[i]=f[i+1]+1.0*n/(n-i); printf("%.2lf\n",f[0]); } return 0; }

本篇博客亦被收进[期望总结][Link 2]

> 如有哪里讲得不是很明白或是有错误，欢迎指正  
> 如您喜欢的话不妨点个赞收藏一下吧

转载于:https://www.cnblogs.com/Morning-Glory/p/11221534.html

[Link 1]: https://blog.csdn.net/Morning_Glory_JR/article/details/96729291
[Link 2]: https://www.cnblogs.com/Morning-Glory/p/11228082.html