P2392

一道有点意思的题......

对于每一科的作业， 左右脑各可以解决一门，最后取花费时间较长的作为全部解决完该科作业的答案，计sum为该科作业时间总和，所以当左右脑各花费sum/2时（也就是时间差为0）答案显然是最优的，所以我们要让这个时间差尽可能的小，所以可以用背包。

设背包容量为sum/2，每个物品的价值和体积都是完成该门作业的时间，f[sum/2]相当于求在sum/2的时间内最多可以完成多少时间的作业，答案累加sum-f[sum/2]即可。

 代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[5], b[30], sum, ans, f[3010];
 4 int main() {
 5     for (int i = 1; i <= 4; i ++) cin >> a[i];
 6     for (int i = 1; i <= 4; i ++) {
 7         sum = 0;
 8         for (int j = 1; j <= a[i]; j ++) {cin >> b[j]; sum += b[j];}
 9         for (int j = 1; j <= a[i]; j ++)//01背包 
10             for (int k = sum / 2; k >= b[j]; k --)    
11                 f[k] = max(f[k], f[k - b[j]] + b[j]);
12         ans += sum - f[sum / 2];
13         for (int j = 1; j <= sum / 2; j ++) f[j] = 0;//清空 
14     }
15     cout << ans << '\n';
16     return 0;
17 }