Codeforces 678E

正文索引 [隐藏]

传送门:http://codeforces.com/problemset/problem/678/E

题目翻译

N个人进行擂台赛,给出每个人对其他人的胜率。
1号选手,可以改变初始擂台主和打擂顺序,请问1号最后站在场上的概率。

题解

状态压缩DP
我们考虑倒过来推,枚举两个对手 i , j (i还在场上而j已经挂了)。i 在他们战斗完依旧站在场上的概率等于 原来 i 在场上 i 打败 j 的概率 + 原来 j 在场上 i 打败 j 的概率
我们用F[i][ST]来表示i在场上现在那些人已经挂了的情况。

代码