「概率,期望DP」总结
2024-10-07 07:49:33
期望=Σ概率*权值
考虑用$f[i][j]$表示princess进行操作时[还剩有i只w,j只b]这一状态的存在概率。这一概率要存在,之前draw out的一定是b,跳出的可能是w可能是b。$ans=\sum\limits f[i][j]*i/(i+j)$
需要注意的是操作时有先后的。由于我们只关心princess,那么上一轮的顺序必须满足princess, dragon, scared mice。
由于i,j都是整数,在处理概率的时候要*1.0或(double)
2. hdu4576
二维DP滚动数组优化一下就好了。
值得注意的是w可能超过n。环形的取模问题。
3. poj2096
可以简化一下这个问题。有n个盒子,每天随机往一个盒子里放东西,问期望几天每个盒子里都有东西。
$f_i=f_i*\dfrac{i}{n}+f_{i+1}*\dfrac{n-i}{n}$
移项可得转移方程。那么本题类似。
Dilute巨爷向我解释了为什么不能正推——因为如果令f[i][j]表示出现在j个软件里出现i种病毒的期望天数,然而这个状态时可以持续的,也就是说可能好几天持续是这个状态。那么期望天数就没有意义了。orz
最新文章
- NOIP2015聪明的质检员[二分 | 预处理]
- mysql学习笔记 第九天
- java 格式化时间
- css3,环绕圆环 loading,小组件
- [redis] 普通 RedisPool 的 CRUD 实现
- C-链表的一些基本操作【创建-删除-打印-插入】
- Poco库之XML操作
- jdbc_odbc SQLserver 驱动安装及测试
- ods_yx给用户分配表空间、权限用户等工作内容。
- 点击某一按钮新增click,并切换页面
- Tsinsen-A1488 : 魔法波【高斯消元+异或方程组】
- 2018-计算机系机试-A
- vue---- v-bind指令
- [转]迄今为止最优的Eclipse运行性能调优 ,含eclipse.ini
- 数组去重--ES5和ES6
- Java_myBatis_一对多映射
- luogu P2325 [SCOI2005]王室联邦
- BZOJ2911 : [Poi1997]The Number of Symmetrical Choices
- 【spoj SUBST1】 New Distinct Substrings
- 算法笔记_209:第六届蓝桥杯软件类决赛部分真题(Java语言B组)