#P3029. 守卫者的挑战 [守卫挑战]

    ID: 2161 传统题 1000ms 512MiB 尝试: 703 已通过: 270 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划概率 DP滚动数组模拟与实现技巧偏移索引CF1800概率期望Poetize1

守卫者的挑战 [守卫挑战]

守卫者的挑战

题目描述

队员们在寻找关押 applepi 的监狱时遇到了黑魔法圣殿的守卫者 Nizem。他将队员们传送到擂台,并留给他们一个容量为 kk 的背包。

擂台上有 nn 项挑战,队员们依次参加。第 ii 项挑战的成功概率为 pi%p_i\%,各项挑战的结果相互独立。挑战失败没有奖励,成功的奖励由整数 aia_i 决定。

  • 若 ai≥0a_i\ge0,队员们得到一个容量为 aia_i 的背包。
  • 若 ai=−1a_i=-1,队员们得到一块大小为 11 的地图残片。

全部挑战结束时,队员们必须至少成功 ll 次,而且所有背包的总容量必须足以装下他们获得的全部地图残片。背包可以有空余容量。求他们能够带着获得的残片离开擂台的概率。

输入格式

第一行三个整数 n,l,kn,l,k,依次表示挑战项数、离开擂台所需的最少成功次数和初始背包容量。

第二行 nn 个实数 p1,…,pnp_1,\ldots,p_n,表示各项挑战的成功概率的百分数值。

第三行 nn 个整数 a1,…,ana_1,\ldots,a_n,表示各项挑战的奖励类型。

输出格式

输出一行一个实数,表示所求概率,四舍五入保留 66 位小数。

数据范围

0≤n≤2000\le n\le200,0≤l≤n0\le l\le n,0≤k≤20000\le k\le2000,−1≤ai≤1000-1\le a_i\le1000,0≤pi≤1000\le p_i\le100。

样例

3 1 0
10 20 30
-1 -1 2
0.300000
5 1 2
36 44 13 83 63
-1 2 -1 2 1
0.980387

样例 1 解释

第三项挑战成功时,队员们至少成功一次,得到的容量 22 足以装下前两项挑战可能获得的至多两块残片。第三项失败时,前两项只要成功一项就会得到无法装下的残片,两项都失败则达不到至少成功一次的要求。因此所求概率就是第三项成功的概率 0.30.3。