tkdsheep-solution-0026

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
Kobe一共要打十场比赛，这十场比赛的环境可能不同，所以即使是同一个对手，Kobe在不同的比赛下战胜这个对手的概率可能不同

Kobe一共有5000个对手，他要从中挑出十个对手来完成这十场比赛，注意如果一个对手在第i场比赛和Kobe相遇，那么他们就不能在剩下的9场比赛相遇，所以这10个对手必须是不同的人

然后对于每场比赛，题目都会告诉你Kobe打败每个人的概率，以及打败每一个人所得到的分数（这个分数对于在任意比赛下打败这个人都是一样的，不同的人分数可能不同）

求Kobe在打赢全部十场比赛的【概率最大】的前提下，得到的总分最高是多少

首先这题有一个优化，就是找出每场比赛Kobe胜率最高的那10个人，十场比赛最多取出100个人，最终答案一定是在这100个人中产生的，这个自己推一下就明白了，这样就把5000优化到了100

标程是用的二分图最佳匹配，我用的是5000*1024的状态压缩dp（可以把5000优化到100）

dp[i][mask]表示前i个人，比赛完成状态为mask的情况下，最大概率是多少，对应的分数是多少

然后一个人一个人去刷新这个dp即可
}}}

Kobe一共要打十场比赛，这十场比赛的环境可能不同，所以即使是同一个对手，Kobe在不同的比赛下战胜这个对手的概率可能不同
Kobe一共有5000个对手，他要从中挑出十个对手来完成这十场比赛，注意如果一个对手在第i场比赛和Kobe相遇，那么他们就不能在剩下的9场比赛相遇，所以这10个对手必须是不同的人
然后对于每场比赛，题目都会告诉你Kobe打败每个人的概率，以及打败每一个人所得到的分数（这个分数对于在任意比赛下打败这个人都是一样的，不同的人分数可能不同）
求Kobe在打赢全部十场比赛的【概率最大】的前提下，得到的总分最高是多少
首先这题有一个优化，就是找出每场比赛Kobe胜率最高的那10个人，十场比赛最多取出100个人，最终答案一定是在这100个人中产生的，这个自己推一下就明白了，这样就把5000优化到了100
标程是用的二分图最佳匹配，我用的是5000*1024的状态压缩dp（可以把5000优化到100）
dp[i][mask]表示前i个人，比赛完成状态为mask的情况下，最大概率是多少，对应的分数是多少
然后一个人一个人去刷新这个dp即可