一辈子都不可能学会期望的

· · 个人记录

一些时候, 从开始到结束的过程中, 经过一个事件的概率并不为1, 因此从如果按开始->结束来dp, 需要计算上概率。

但实际上, 从一个事件到结束的概率一定为1(一定会结束), 因此如果我们按照形如:设 f(A)代表从A到结束的期望代价, 那么p(A)为1

例子是求有向图从起点到终点的期望步数, 到了一个点之后走边的概率是相同的.按照上面所说, 设f[i]代表从i到n的期望步数, 那么f[u] = sigma(v) (f[v] + e[i].w) / deg_u