信息
- ID
- 151
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
直接 22n 枚举每天选的东西,然后求答案即可。
考虑设 fi,j 表示前 i 天,语文选了 j 次此时的最大价值。
然后转移就是 $f_{i, j} = \max(f_{i - 1, j - 1} + a_i, f_{i - 1, j} + b_i)$。
答案就是 f2n,n。
时间复杂度 O(n2)。
考虑一个贪心:
先全选语文,然后拿出一些换成数学。
那么每个换成数学的贡献就是 bi−ai,我们对这个排序,然后贪心取最大的 n 个即可。
时间复杂度 O(nlogn)。