1 条题解

  • 0
    @ 2026-11-15 15:17:20

    题目分析

    考点:动态规划、背包。

    测试点 1~3:给暴力搜索留的分。

    测试点 4~7:给暴力讨论的部分分。对于每一天,小 C 可以选择翘若干节课、少呆若干个小时。贪心地选择「少呆时间最长」的课,最后如果还能翘课,那么多余的课都只能少呆固定的时长。

    测试点 8~11:进一步扩展。对每一天,枚举每节课翘或不翘,暴力预处理出 ff 数组,表示这一天翘掉若干节课时,小 C 在教学楼里最少需要呆多少小时。之后就是一个分组背包:每组(每天)内只能选择一种方案,组间做背包合并。时间复杂度 O(n2)O(n^2) 级别。

    测试点 12~13、17~20:不必暴力枚举每节课的取舍,只需考虑这一天中「最早的课」和「最晚的课」分别是哪一节即可——中间被翘掉的课不会减少呆在教学楼里的总时间。于是枚举最早的课与最晚的课,直接算出需要翘多少节课,并求出此时小 C 在教学楼里需要呆的时长。这样可以在 O(n2)O(n^2) 内求出所有方案,再配合分组背包得到最终答案。

    • 1

    信息

    ID
    111
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者