#P12282. [蓝桥杯 2024 国 Python A] 羊圈

    ID: 13938 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>2024Special Judge期望蓝桥杯国赛状压 DP

[蓝桥杯 2024 国 Python A] 羊圈

题目描述

小蓝养了 mm 头羊,它们站成一排,第 ii 头羊有 pip_i 的概率跑掉。小蓝为了不让他的羊跑掉,购买了 nn 个羊圈,第 ii 个羊圈最多可以框住连续的 lil_i 只羊,让它们无法逃跑。小蓝想知道,在合理安排羊圈位置的情况下,能跑掉的羊的数量的期望的最小值是多少?

请注意:羊圈不一定都使用,也不一定按顺序使用。

输入格式

输入的第一行包含两个正整数 n,mn, m,用一个空格分隔。

第二行包含 nn 个正整数 l1,l2,,lnl_1, l_2, \cdots, l_n,相邻整数之间使用一个空格分隔。

第三行包含 mm 个浮点数 p1,p2,,pmp_1, p_2, \cdots, p_m,每个浮点数小数点后不超过 22 位小数,相邻浮点数之间使用一个空格分隔。

输出格式

输出一行包含一个浮点数表示答案,四舍五入保留正好两位小数。

3 10
1 2 3
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
1.00

提示

样例说明

第一个羊圈框住第 55 头羊,第二个羊圈框住第 99 至第 1010 头羊,第三个羊圈框住第 66 至第 88 头羊,剩下的羊逃跑的数量的期望为 0.1+0.2+0.3+0.4=1.00.1 + 0.2 + 0.3 + 0.4 = 1.0

评测用例规模与约定

  • 对于 20%20\% 的评测用例,1n81 \leq n \leq 8
  • 对于所有评测用例,1n151 \leq n \leq 151m2001 \leq m \leq 2001lim1 \leq l_i \leq m0pi10 \leq p_i \leq 1