BZOJ 5199 [NWERC2017]Knockout Tournament

发布于 2018-03-04  244 次阅读


题意:http://www.lydsy.com/JudgeOnline/problem.php?id=5199

题意:安排一个淘汰赛顺序,使得你赢面最大。


轮空情况视为干一个战斗力为 0 的人,显然贪心的让自己尽可能干战斗力低的人,排序一下就知道第一轮情况了。

然后 dp 转移,\(p_{i,j}\) 表示 j 这个人一直赢到了第 i 轮的概率。

转移的时候找到哪些是可能的 j,有点麻烦...

 


一个非常弱的准退役OIER