引入
举一个求期望最简单的例子:
假设有个人在 1号节点处,每一分钟他会缘着边随机走到一个节点或者在原地停留,问他走到4号节点需要平均几分钟?
这是个简单的期望问题,我们用 Ei(i=1,2,3,4) 表示从i号节点走到4号节点的数学期望值。根据题意对1号节点有
①
表示他下一分钟可以走到2或者3或在原地1,每个可能概率是1/3 ,注意是下一分钟,故要加上1。
同理我们对节点2,3同样可以列出
②
③
因为E4=0,这样上面1234式其实就是组成了一组方程组,解方程组就可得出E1,用高斯消元,复杂度是。
从上述例子,我们可总结出如何解决期望类问题,根据题意,表示出各个状态的期望(上例的Ei(i=1,2,3,4)),根据概率公式,列出期望之间的方程,解方程即可。
当我们把各个状态当成是一个个节点时,概率关系为有向边,我们可看到,可递推的问题其实就是这个关系图是无环的!那必须要用方程组解决的问题其实就是存在环! 而且还要指出的是用高斯消元的时候,要注意误差的问题,最好把式子适当的增大,避免解小数,否则误差太大,估计也会卡题。
题目
LightOj1027
题意:
有n扇门,正数的门可以时间把人带到终点,负数的门可以时间把人带回起点,问到终点的时间的期望为多少。
思路:
设期望为E。
比如样例3 -6 -9,是这样求期望的,解一下方程就可以了。解释一下这个是为什么,因为被带回到起点,就相当于重新开始选择,所以时间就是。
牛客小白赛8G
题意:
微信抢红包,有一个红包可以被m个人领取,而且红包的总金额是n。如果为第k个抢红包的人时候,所抢到红包金额的期望是多少?(红包的大小在中均匀随机,特别的当红包的大小小于时,最后剩下的金额会被包入最后一个红包中)。
思路:
:剩余i元,还有j个红包,在第k个抢到的期望。
有转移:
。
手推:
k=2。
k=1的时候好算,为。
k=2:
。
即。
因为与k无关,之后的过程是一样的,所以答案为。
POJ2096
题意:
有A物品数量为a,B物品数量为b,一个人每天可以得到一个A物品和一个B物品,问得到所有物品的天数期望是多少。
思路:
:已经得到了i个A物品和j个B物品要得到所有物品的天数期望。
E(n,s)=0,要求E(0,0)。
有四种情况的转移:没发现任何新的bug和子组件;发现一个新的bug;发现一个新的子组件;同时发现一个新的bug和子组件。
可以列出式子:
。
把E(i,j)移项到左边,就可以得到E(i,j)的表达式。
然后递推一下就可以了。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!