关于期望DP
  • 板块灌水区
  • 楼主cmh2667903441
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/9 08:56
  • 上次更新2023/11/9 09:59:08
查看原帖
关于期望DP
187976
cmh2667903441楼主2023/11/9 08:56

做noip模拟赛 遇到期望DP总是跳 所以来咨询一下关于期望DP的一些问题


给出张 n 个点m 条边的有向无环图,起点为1,终点为n,
每条边都有一个长度,并且从起点出发能够到达所有的点,
所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。 
到达每一个顶点时,如果该节点有k 条出边,
绿豆蛙可以选择任意一条边离开该点,
并且走向每条边的概率为1/k
 现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

比如上题

E(i)表示从1到i的期望长度

已知u->v有边 且知道了E(u)

请问E(v)是等于E(u)+1/k嘛

2023/11/9 08:56
加载中...