1 条题解
-
0
题目分析
考点:动态规划、背包。
测试点 1~3:给暴力搜索留的分。
测试点 4~7:给暴力讨论的部分分。对于每一天,小 C 可以选择翘若干节课、少呆若干个小时。贪心地选择「少呆时间最长」的课,最后如果还能翘课,那么多余的课都只能少呆固定的时长。
测试点 8~11:进一步扩展。对每一天,枚举每节课翘或不翘,暴力预处理出 数组,表示这一天翘掉若干节课时,小 C 在教学楼里最少需要呆多少小时。之后就是一个分组背包:每组(每天)内只能选择一种方案,组间做背包合并。时间复杂度 级别。
测试点 12~13、17~20:不必暴力枚举每节课的取舍,只需考虑这一天中「最早的课」和「最晚的课」分别是哪一节即可——中间被翘掉的课不会减少呆在教学楼里的总时间。于是枚举最早的课与最晚的课,直接算出需要翘多少节课,并求出此时小 C 在教学楼里需要呆的时长。这样可以在 内求出所有方案,再配合分组背包得到最终答案。
- 1
信息
- ID
- 111
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者