CF605E Intergalaxy Trips

标签:galaxy   sum   存在   策略   rac   应该   int   font   size   

很不错的期望题

先设i号节点到达n号节点的期望步数为E[i]

由于每次选择的都是最优策略

所以得到一个性质:若在某一时刻i号节点到j号、k号节点的道路都存在时,一定选择E数组较小的那个

由此可以得到一个小柿子:

$E[i]=\sum\limits_{E[j]<E[i]} E[j]*p(i,j) * \prod\limits_{E[k]<E[j]}[1-p(i,j)]$

这是第一时刻就有i->j这条路的期望,所以这个狮子应该再乘上一个$\frac{1}{1-\prod\limits_{E[k]<E[j]}(1-p(i,k))}$

这个东西蛮难理解的,字面意思是j和所有E数组的值比j小的k至少有一个节点能有i抵达的期望

你或许可以理解为E[j]、E[k]都不出现n轮的期望

感觉这样稍微好理解一点

然后狮子就变成了$E[i]=\sum\limits_{E[j]<E[i]} E[j]* \frac{p(i,j)}{1-\prod\limits_{E[k]<E[j]}(1-p(i,k))}* \prod\limits_{E[k]<E[j]}[1-p(i,j)]$

好像做完了

CF605E Intergalaxy Trips

标签:galaxy   sum   存在   策略   rac   应该   int   font   size   

原文地址:https://www.cnblogs.com/handsome-zlk/p/14229178.html

版权声明:完美者 发表于 2021-01-07 11:54:16。
转载请注明:CF605E Intergalaxy Trips | 完美导航

暂无评论

暂无评论...