[RC-02] 开门大吉
题目描述
$n$ 位选手去参加节目“开门大吉”。共有 $m$ 套题,每套题包含 $p$ 个题目,第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。
若一位选手答对第 $i$ 题,会在已得到奖励的基础上,再得到 $c_i$ 元奖励。选手总是从第一道开始,按顺序答题的。
同时,为了防止过多的选手做同一套题,还有 $y$ 条形如“第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$”的限制。
你需要给每一位选手分配一套题(不同选手可以相同),使得所有人的期望奖励和最小。
输入输出格式
输入格式
输入包含多组数据。第一行是一个整数 $T$,为数据组数。
对于每组数据,第一行四个整数 $n,m,p,y$。
接下来一行 $p$ 个整数,第 $i$ 个为 $c_i$。
接下来 $m$ 个 $n\times p$ 的矩阵,第 $j$ 个矩阵中第 $i$ 行第 $k$ 个实数为 $f_{i,j,k}$。
接下来 $y$ 行,每行三个整数 $i,j,k$($1\le i,j\le n$,$-m<k<m$),描述一条限制。
输出格式
对于每组数据,输出一个实数,为答案。无解输出 `-1`。
本题有 Special Judge,答案误差在 $5\times 10^{-4}$ 以内都算对。
由于 SPJ 敏感,请在每组数据末尾都输出一个换行符,并不要再输出其它字符。
输入输出样例
输入样例 #1
4
3 2 4 0
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
3 2 4 1
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
2 3 1
3 2 4 1
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
1 2 1
3 2 4 2
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
1 2 1
2 3 1
输出样例 #1
15.1460
18.5340
18.7560
-1
说明
【样例解释】
这里只解释第二组数据。
一共只有两套题,而第二个人的套题编号大于第三个人,因此第二个人一定是选第二套,第三个人选第一套。
第二个人选第二套,期望支出:$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$。