HOJ-P1113-期望dp
题目大意
\(n\) 人参加 \(m\) 轮比赛，第 \(i\) 个人在第 \(j\) 场比赛拿到 \(k\) 分的概率是 \(a_{i,j,k}\)，每一场比赛有且只有一人能够拿分，求 \(m\) 场比赛结束后选手中最高分的期望是多少。
保证 \(\forall i\in[1,m],\sum\limits_{j=1}^n\sum\limits_{k=1}^3 a_{j,i,k}=1\)
\(1\le n\le 20,1\le m\le 10,1\le k\le 3\)
解题思路
看到如此小的 \(m\)，可以想到状压dp。
因为最终答案要求的是最大值的期望，所以我们可以考虑用一维存储最大值，\(f\) 的值表示到达该状态的概率，求期望时将两项相乘求和即可。
但是如果将每个人 "分配" 给每场比赛，会发现并不好转移，所以我们考虑反过来，枚举每个人，再定赢了哪些比赛。
所以我们可以想到令 \(f_{i,j,k,w}\) 表示枚举到第 \(i\) 个人，第 \(i\) 个人得了 \(j\) 分，前 \(i\) 个人中最高分为 \(k\)，\(w\) 这些比赛的胜者已经确定的概率。
细节
代码