【HDU4652】Dice(数学期望,动态规划)
规划 动态 数学 期望
2023-09-11 14:14:41 时间
【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=1,d=1;
for(register int j=1;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));
}
}
相关文章
- 【CF1152F】Neko Rules the Catniverse(动态规划)
- 【CF1133E】K Balanced Teams(动态规划,单调队列)
- 【CF809D】Hitchhiking in the Baltic States(Splay,动态规划)
- 【BZOJ5471】[FJOI2018]邮递员问题(动态规划)
- 【BZOJ1802】[AHOI2009]checker(动态规划)
- 【BZOJ1864】三色二叉树(动态规划)
- 【BZOJ2024】舞会(动态规划,容斥,高精度)
- 【BZOJ1048】分割矩阵(记忆化搜索,动态规划)
- 【BZOJ3156】防御准备(动态规划,斜率优化)
- 【Luogu1291】百事世界杯之旅(动态规划,数学期望)
- 【算法】【递归与动态规划模块】换钱的最小硬币数
- 【CF724F】Uniformly Branched Trees 动态规划
- 【PSO路径规划】基于PSO优化算法的动态路径规划MATLAB仿真
- C#,动态规划(DP)金矿问题(Gold Mine Problem)的算法与源代码
- 最大子段和-分治&&动态规划
- 动态规划之矩阵连乘问题
- 《企业大数据系统构建实战:技术、架构、实施与应用》——第2章 企业大数据职能规划 2.1 大数据组织架构体系
- 四足机器人足端轨迹规划--摆线
- Python—数据结构与算法---动态规划—DP算法(Dynamic Programing)
- LeetCode动态规划基础题-基础题
- LeetCode010之正则表达式(相关话题:动态规划,类比思维)
- 164、【动态规划】leetcode ——213. 打家劫舍 II:环形列表线性化(C++版本)
- 155、【动态规划】leetcode ——474. 一和零:三维数组+二维滚动数组(C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- 人生规划或人生的职业规划
- 迁移云端,关于容量规划、灾难恢复你都想好了吗?
- 12动态规划运用实例