【OI之路】07动态规划-5概率与期望

概率与期望

概率

应该不难?

期望

通俗地讲,就是【所有结果状态的权值乘以概率】的和
相当于,尝试无限次后,得到的平均数
通常是倒推的,因为这样,当前状态的概率总是1,灰常方便

例题:3801 Rainbow的信号

然后讲讲期望的线性性
结合例题:3802 绿豆蛙的归宿
对于一个状态x,如果按照定义来计算期望
枚举它的所有能产生的结果状态,然后累计权值乘以概率

然鹅事实上可以直接枚举k个后继状态y
$f[x]=\sum_{i=1}^k (f[y_i]+c)\times \frac{1}{k}$
这是为什么?其实就是把c按照后面发生的概率,
等比例划分后更新到权值里面(因为权值也就是距离在变大)

有空再慢慢研究的资料

练习题

Tag-概率与期望

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7366.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%