P2392 kkksc03考前临时抱佛脚
P2392 kkksc03考前临时抱佛脚 - 洛谷
借鉴题解 P2392 kkksc03考前临时抱佛脚 - 洛谷
自用笔记
这是一道将每一刻题目尽量两两并作、以最短时间完成所有题目的。每一刻题目都做一次“将题目划分成左右两组，使两组耗时差最小”的0.1背包问题
💡 题目本质
题目说：每一科题目只能在这科内部用双核（左右脑）并行做两题，但不同科不能同时做。
我们要最小化总时间。
✅ 关键点：
对于每一科的题目集合 T，我们要：
-
把题目划分成两个子集
L和R，分别给左右脑 -
两个脑子可以同时进行
-
所以这一科的总耗时是
max( sum(L), sum(R) )，即两个子集的总和中较大的一个
于是我们想让两组总时间差尽可能小，就能最小化这科复习时间。
✅ 所以这是个子集划分问题 —— 0/1 背包
你用了背包算法，目的是：
-
在这科题目总时间为
S的基础上 -
选出一个子集，总时间不超过
S / 2，使得该子集时间最大
设这个最大值为 t，那另一个子集就是 S - t
-
所以该科复习时间为：
max(t, S - t)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
#define ll long long
int f[21][1301];
int a[4],b[100];
int main()
{ios::sync_with_stdio(false);for(int i=1;i<=4;i++) cin>>a[i];int res=0;for(int i=1;i<=4;i++){int s=0;for(int j=1;j<=a[i];j++)cin>>b[j],s+=b[j];int t=0;for(int j=1;j<=a[i];j++)for(int k=0;k<=s/2;k++){f[j][k]=f[j-1][k];if(k>=b[j])f[j][k]=max(f[j][k],f[j-1][k-b[j]]+b[j]);t=max(f[j][k],t);}res+=max(t,s-t);}cout<<res;return 0;
}