P2392 kkksc03考前临时抱佛脚

经典的 01 背包问题。

一开始当贪心瞎写成功写出了全红

不过题解还是有点没看懂

说来也巧，做题的时间倒也是紧贴考试（蓝桥杯校赛），略难绷

What can I say?

// Problem: P2392 kkksc03考前临时抱佛脚
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2392
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cmath>
using namespace std;
int backpack[114514];
int main(){
	int ans = 0;
	int count[4];
	for(int l=0;l<4;l++){
		cin>>count[l];
	}
	for(int l=0;l<4;l++){
		int tmp[21];
		int total = 0;
		for(int i=0;i<count[l];i++){
			cin>>tmp[i];
			total+=tmp[i];
		}
		for(int i=0;i<count[l];i++){
			for(int p=total/2;p>=tmp[i];p--){
				backpack[p] = max(backpack[p], backpack[p-tmp[i]] + tmp[i]);
			}
		}
		ans+=max(total - backpack[total/2], backpack[total/2]);
		cerr<<ans<<endl;
		for(int i=0;i<114514;i++){
			backpack[i] = 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}