【HDU4652】Dice(数学期望,动态规划)
【HDU4652】Dice(数学期望,动态规划)
题面
Vjudge
有一个\(m\)面骰子
询问,连续出现\(n\)个相同的时候停止的期望
连续出现\(n\)个不同的时候停止的期望
题解
考虑两种分开询问来算。
第一种:
设\(f[i]\)表示已经有连续的\(i\)个相同时,到达目标状态的期望。
\[f[i]=\frac{1}{m}f[i+1]+\frac{m-1}{m}f[1]+1\]
相邻两项作差,得到
\[m(f[i+1]-f[i])=f[i+2]-f[i+1]\]
按照顺序列出来
\(f[0]-f[1]=1\)
\(f[1]-f[2]=m\)
\(f[2]-f[3]=m^2\)
...
\(f[n-1]-f[n]=m^{n-1}\)
将所有式子相加起来
\(f[0]-f[n]=\frac{m^n-1}{1-m}\)
\(f[n]=0\),这样就知道了\(f[0]\)
所以
\[Ans=f[0]=\frac{m^n-1}{1-m}\]
考虑第二种询问
设\(f[i]\)表示连续\(i\)个不同的数字,到达目标状态的期望
\[f[i]=\frac{m-i}{m}f[i+1]+\frac{f[1]+f[2]+f[3]+...f[i-1]+f[i]}{m}\]
还是相邻两项作差让后相加,算出答案
\[Ans=\sum_{i=0}^{n-1}\prod_{j=0}^{i}\frac{m}{m-j}\]
#include<cstdio> #include<cmath> using namespace std; double Solve1(int m,int n){return (pow(m,n)-1.0)/(m-1.0);} double Solve2(int m,int n) { double ret=,d=; for(register int j=;j<n;++j)d=1.0*m/(m-j)*d,ret+=d; return ret; } int main() { register int T,opt,n,m; while(scanf("%d",&T)!=EOF)while(T--) { scanf("%d%d%d",&opt,&m,&n); printf("%.9lf\n",!opt?Solve1(m,n):Solve2(m,n)); } }
相关推荐
yedaoxiaodi 2020-07-26
us0 2020-06-25
Eduenth 2020-06-22
Oudasheng 2020-06-13
sunjunior 2020-05-19
chenfei0 2020-04-30
老和山下的小学童 2020-04-20
SystemArchitect 2020-04-14
jiayuqicz 2020-02-02
zangdaiyang 2020-01-25
yuanran0 2020-01-20
yedaoxiaodi 2020-01-12
rein0 2020-01-01
Oudasheng 2019-12-27
Oudasheng 2019-12-22
wuxiaosi0 2019-12-17
trillionpower 2019-11-23
ustbfym 2019-11-03