黑魔法圣殿的挑战

题目描述

打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。

突然，眼前一道亮光闪过，"我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……"。

瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 $K$ 的包包。

挑战规则

擂台赛一共有 $N$ 项挑战，各项挑战依次进行。

第 $i$ 项挑战有一个属性 $a_i$：

• 如果 $a_i \ge 0$，表示这次挑战成功后可以再获得一个容量为 $a_i$ 的包包
• 如果 $a_i = -1$，则表示这次挑战成功后可以得到一个大小为 $1$ 的地图残片

携带规则

• 地图残片必须装在包包里才能带出擂台
• 包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走
• 只需要完成所有 $N$ 项挑战后背包容量足够容纳地图残片即可
• 他们至少要挑战成功 $L$ 次才能离开擂台

挑战成功概率

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 $i$ 项挑战成功的概率为 $p_i\%$。

问题

现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

输入格式

第一行三个整数 $N, L, K$。

第二行 $N$ 个实数，第 $i$ 个实数 $p_i$ 表示第 $i$ 项挑战成功的概率的百分比。

第三行 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 项挑战的属性值。

输出格式

一个实数，表示所求概率，四舍五入保留 $6$ 位小数。

数据范围

• $0 \le K \le 2000$
• $0 \le N \le 200$
• $-1 \le a_i \le 1000$
• $0 \le L \le N$
• $0 \le p_i \le 100$

输入样例

3 1 0
10 20 30
-1 -1 2

输出样例

0.300000

样例解释

输入数据

• $N = 3$：3项挑战
• $L = 1$：至少成功1次才能离开
• $K = 0$：初始包包容量为0

挑战成功概率（百分比）：

• 第1项：$10\%$（$p_1 = 10$）
• 第2项：$20\%$（$p_2 = 20$）
• 第3项：$30\%$（$p_3 = 30$）

挑战属性：

• 第1项：$a_1 = -1$（成功得地图残片）
• 第2项：$a_2 = -1$（成功得地图残片）
• 第3项：$a_3 = 2$（成功得容量为2的包包）

计算分析

要求：

1. 至少成功 $L=1$ 次
2. 最终包包容量要足够容纳所有获得的地图残片

初始状态：包包容量 $K=0$

考虑各种情况：

情况1：只成功第1项挑战

• 概率：$10\% \times (1-20\%) \times (1-30\%) = 0.10 \times 0.80 \times 0.70 = 0.056$
• 成功次数：1次（满足至少1次）
• 获得：1个地图残片（需要容量1）
• 包包容量：初始0，没有获得新包包
• 最终容量0 < 需要容量1，无法带走，概率为0

情况2：只成功第2项挑战

• 概率：$(1-10\%) \times 20\% \times (1-30\%) = 0.90 \times 0.20 \times 0.70 = 0.126$
• 成功次数：1次（满足）
• 获得：1个地图残片（需要容量1）
• 包包容量：0
• 0 < 1，无法带走，概率为0

情况3：只成功第3项挑战

• 概率：$(1-10\%) \times (1-20\%) \times 30\% = 0.90 \times 0.80 \times 0.30 = 0.216$
• 成功次数：1次（满足）
• 获得：容量为2的包包
• 地图残片：0个（需要容量0）
• 包包容量：初始0 + 2 = 2
• 2 ≥ 0，可以带走，概率为0.216

情况4：成功第1和第2项挑战

• 概率：$10\% \times 20\% \times (1-30\%) = 0.10 \times 0.20 \times 0.70 = 0.014$
• 成功次数：2次（满足）
• 获得：2个地图残片（需要容量2）
• 包包容量：0
• 0 < 2，无法带走，概率为0

情况5：成功第1和第3项挑战

• 概率：$10\% \times (1-20\%) \times 30\% = 0.10 \times 0.80 \times 0.30 = 0.024$
• 成功次数：2次（满足）
• 获得：1个地图残片 + 容量为2的包包
• 需要容量：1
• 包包容量：0 + 2 = 2
• 2 ≥ 1，可以带走，概率为0.024

情况6：成功第2和第3项挑战

• 概率：$(1-10\%) \times 20\% \times 30\% = 0.90 \times 0.20 \times 0.30 = 0.054$
• 成功次数：2次（满足）
• 获得：1个地图残片 + 容量为2的包包
• 需要容量：1
• 包包容量：0 + 2 = 2
• 2 ≥ 1，可以带走，概率为0.054

情况7：成功所有3项挑战

• 概率：$10\% \times 20\% \times 30\% = 0.10 \times 0.20 \times 0.30 = 0.006$
• 成功次数：3次（满足）
• 获得：2个地图残片 + 容量为2的包包
• 需要容量：2
• 包包容量：0 + 2 = 2
• 2 ≥ 2，可以带走，概率为0.006

情况8：全部失败

• 概率：$(1-10\%) \times (1-20\%) \times (1-30\%) = 0.90 \times 0.80 \times 0.70 = 0.504$
• 成功次数：0次（不满足至少1次）
• 概率为0

总成功概率

可以带走的情况：情况3 + 情况5 + 情况6 + 情况7

• $0.216 + 0.024 + 0.054 + 0.006 = 0.300$

输出：0.300000

问题建模

这是一个概率DP问题。

状态定义

设 $dp[i][j][c]$ 表示：

• 完成了前 $i$ 项挑战
• 成功了 $j$ 次
• 当前包包容量为 $c$ 的概率

状态转移

对于第 $i$ 项挑战：

1. 挑战成功（概率 $p_i/100$）：
   • 如果 $a_i = -1$：获得地图残片，需要容量+1（但包包容量不变）
   • 如果 $a_i \ge 0$：获得容量为 $a_i$ 的包包，包包容量增加
   • 成功次数 $j$ 增加1
2. 挑战失败（概率 $1 - p_i/100$）：
   • 状态不变

边界条件

• 初始状态：$dp[0][0][K] = 1$（未开始挑战，成功0次，包包容量为初始K）
• 包包容量上限：由于 $a_i \le 1000$，$N \le 200$，最大可能容量为 $K + 200 \times 1000$，但实际可以限制
• 地图残片数量：最多 $N$ 个（如果所有 $a_i=-1$ 的挑战都成功）

最终答案

完成所有 $N$ 项挑战后，满足：

1. 成功次数 $j \ge L$
2. 包包容量 $c \ge$ 获得的地图残片总数

对所有满足条件的 $dp[N][j][c]$ 求和。

优化

• 包包容量可以压缩：当容量超过 $N$ 时（因为最多 $N$ 个地图残片），多余的容量无用
• 地图残片数量可以记录在状态中，或者计算最终容量要求

时空限制

• 时间限制：1秒
• 空间限制：64MB