1 条题解

  • 0
    @ 2026-11-15 17:54:51

    题目分析

    对于 10%10\%

    直接 22n2^{2n} 枚举每天选的东西,然后求答案即可。

    对于 40%40\%

    考虑设 fi,jf_{i, j} 表示前 ii 天,语文选了 jj 次此时的最大价值。

    然后转移就是 $f_{i, j} = \max(f_{i - 1, j - 1} + a_i, f_{i - 1, j} + b_i)$。

    答案就是 f2n,nf_{2n,n}。

    时间复杂度 O(n2)O(n^2)。

    对于 100%100\%

    考虑一个贪心:

    先全选语文,然后拿出一些换成数学。

    那么每个换成数学的贡献就是 bi−aib_i - a_i,我们对这个排序,然后贪心取最大的 nn 个即可。

    时间复杂度 O(nlog⁡n)O(n\log n)。

    • 1

    信息

    ID
    151
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者