2022 天梯赛选拔赛

Problem E. 星月选课(15分)

在第五轮选课结束后,白茶发现全部选修课都被退选了,他绝望地喊出 “日内瓦,退学!”。冷静过后,他认为:此诚危急存亡之秋也。于是,白茶开始认真思考往后如何才能凑够学分。他花费一个时间戳单位就想出了结论。为了检验星月逻辑训练的成果,白茶想让星月解决这个问题。

已知还有 n 门选修课可选,第 i 门课的学分是 w_i ,选中的概率是 p_i 。每门课可选可不选,且假设白茶从不挂科。请问,它能获得的学分的最大数学期望值是多少?

输入

输入一行一个整数 n(1\le n\le10^4) ,代表课程数。

接下来输入一行 n 个整数,第 i 个整数代表第 i 门课的学分 w_i(1\le w_i\le8)

接下来输入一行 n 个一位小数,第 i 个实数代表第 i 门课的选中概率 p_i(0.1\le p_i\le1.0)

输出

输出一行一个实数代表最大学分的数学期望值。你的答案被认为是正确的当且仅当你的答案与标准答案的相对误差或绝对误差其一不超过 0.01

样例

标准输入 复制文本
2
2 3
0.5 0.5
标准输出 复制文本
2.5

提示

假设两门课都选,有四种情况:

  • 第一门选上第二门选上,得 5 学分
  • 第一门选上第二门落选,得 2 学分
  • 第一门落选第二门选上,得 3 学分
  • 第一门落选第二门落选,得 0 学分

p=0.5 ,四种情况等概率,期望值为 (5+2+3+0)\div 4=2.5 学分

假设只选第一门课,要么选上得 2 学分,要么落选没分,期望值为 1 学分

假设只选第二门课,要么选上得 3 学分,要么落选没分,期望值为 1.5 学分

假设不选,得 0 学分。

在所有四种选课方案里,第一种最优,其期望值为 2.5 学分。

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 81
通过 64

A B C D E F G H I J K L M N O

题目存在部分分,请使用合适的做题策略答题