【题解】期末考试抱佛脚最短时间（动态规划 | 二进制背包）
题目链接
题目背景
kkksc03 的大学生活非常颓废，临近期末考试才开始疯狂复习。他有 4 门科目需要复习，每一科都有若干道题目，每道题目需要一定的时间完成。
幸运的是，kkksc03 有一个独特的能力：左右大脑可以同时计算两道不同的题目（但仅限于同一门科目），也就是说，同一时间可以同时做两道不同的题目。
为了能尽快开始处理洛谷上的 bug，他希望以最短的总时间完成所有复习工作。
题目描述
给定 4 门科目的题目数量和每道题目所需时间，kkksc03 必须一科一科地复习（不能同时跨科目），并且每一科允许左右脑同时处理不同的题目。
求出完成所有科目的最短总复习时间。
输入格式
- 第 1 行：四个正整数 s₁, s₂, s₃, s₄，分别表示第 1~4 科的题目数。
- 第 2-5 行：分别给出每门科目的每道题目的完成时间。
输入样例
1 2 1 3
5
4 3
6
2 4 3
输出格式
一行一个整数，表示复习完所有科目的最短时间。
输出样例
20
题目分析
这道题的核心是：
- 每一科单独处理，不能跨科目并行。
- 每一科允许左右脑同时处理两道不同的题目，等价于把题目集合分成两个子集，让两个子集的时间总量尽量平衡。
这很像背包问题！
进一步理解：
- 如果一个科目总时间是
sum，我们可以把所有题目划分成两部分，使得两部分的时间尽可能接近。 - 最慢的那部分时间，决定了完成这一科目的所需时间。
- 也就是：某一部分时间最长为 sum/2 的最大可达值 x，所需时间就是 max(x, sum - x)。
- 因为左右脑是同步进行的，所以总时间就是其中较大的那部分时间。
总结一下，每一科是独立的小问题，每一科本质上是一个0-1 背包问题，背包容量是 sum/2。
解题思路
- 对于每一科，读取所有题目的时间。
- 计算所有题目时间的总和
sum。 - 使用
dp[i]表示是否可以恰好达到时间i。 - 标准的 0-1 背包过程，从大到小枚举。
- 找到不超过
sum/2的最大可达时间x。 - 当前科目的最短时间为
max(x, sum-x)。 - 累加到总时间。
AC代码讲解
#include<bits/stdc++.h>
using namespace std;int main()
{int dp[1000] = { 0 }; // 背包DP数组，大小足够int time[22] = { 0 }; // 存储每科的各题时间，最多20题int s[5] = { 0 }; // 四门科目题目数量int ans = 0; // 最后答案// 输入每科题目数量cin >> s[1] >> s[2] >> s[3] >> s[4];for (int t = 1; t <= 4; ++t) // 处理4门科目{int sum = 0;for (int i = 1; i <= s[t]; ++i) // 输入每道题目所需时间{cin >> time[i];sum += time[i];}// 0-1 背包求尽量接近 sum/2 的最大时间for (int j = 1; j <= s[t]; ++j){for (int i = sum / 2; i >= time[j]; --i){dp[i] = max(dp[i], dp[i - time[j]] + time[j]);}}int temp = sum - dp[sum / 2]; // temp 是两个集合时间差较大的那部分ans += max(dp[sum/2], temp); // 加上每科最短时间// 清空dp数组，准备下一科for (int i = 1; i <= sum/2; ++i) dp[i] = 0;}cout << ans;return 0;
}
复杂度分析
- 单科学习部分的时间复杂度为 O(题目数 × 总时间/2)，由于
题目数 <= 20单题时间 <= 60- 所以总时间最多是 20 × 60 = 1200，sum/2 最多600。
- 因此在最坏情况下，单科DP是 O(20×600)=12000，四科一起大约 48000，运行非常快，可以轻松通过！
总结
- 本题本质是每科单独的背包问题。
- 充分理解左右脑同步处理的能力，将问题转化为集合划分问题。
- 小数据量背包，暴力DP即可！
如果你掌握了这一类背包技巧，很多像 “集合划分”、“最大平均值”、“划分集合使得子集和最接近” 等问题都可以迎刃而解！
如果你想要，我还可以帮你附一版更简洁版代码！要不要？✨
