P6054 [RC-02] 开门大吉

$n$ 位选手去参加节目“开门大吉”。共有 $m$ 套题，每套题包含 $p$ 个题目，第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。 若一位选手答对第 $i$ 题，会在已得到奖励的基础上，再得到 $c_i$ 元奖励。选手总是从第一道开始，按顺序答题的。 同时，为了防止过多的选手做同一套题，还有 $y$ 条形如“第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$”的限制。 你需要给每一位选手分配一套题（不同选手可以相同），使得所有人的期望奖励和最小。

无

无

【样例解释】 这里只解释第二组数据。 一共只有两套题，而第二个人的套题编号大于第三个人，因此第二个人一定是选第二套，第三个人选第一套。 第二个人选第二套，期望支出：$0.2\times (1-0.5)\times 10+0.2\times 0.5 \times (1-0.3) \times 20+0.2\times 0.5 \times 0.3\times (1-0.6) \times 30+0.2\times 0.5 \times 0.3\times 0.6 \times 50=3.66$。 其他人的计算方法类似。 【数据范围】 **本题捆绑测试。** 对于所有数据，$1\le n,m,p\le 80$，$0\le y\le 10^3$，$0\le f_{i,j,k} \le 1$，$0\le c_i\le 10^5$，$1 \le T\le 50$。保证每个测试点的输入数据大小小于 $10\text{MB}$。 Subtask 1（20 pts）：$n,m,p,y\le 7$； Subtask 2（20 pts）：$T\le 6$，$y=0$； Subtask 3（20 pts）：$n,m,p\le 30$，$y\le 200$； Subtask 4（20 pts）：$T=1$； Subtask 5（20 pts）：$T\le 5$。