P2392 kkksc03考前临时抱佛脚——洛谷

P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

//不要着急，耐心一点，相信自己，不要摆烂，一定要坚持
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int>dp;
int a[10000],b[10000];
int main(){for(int i=0;i<4;i++)cin>>a[i];int ans=0;for(int i=0;i<4;i++){int sum=0;for(int j=0;j<a[i];j++){cin>>b[j];sum+=b[j];}//从贪心的角度思考，我们希望平衡左右脑的时间，即左右脑时间差要尽量小//因此我们取时间的一半，去计算某一半脑的时间（尽量靠近一半时间）能有多大for(int j=0;j<a[i];j++){for(int k=sum/2;k>=b[j];k--)dp[k]=max(dp[k],dp[k-b[j]]+b[j]);//下标为时间，内容也是时间，（即价值和体积都是时间）}int op=sum-dp[sum/2];//加上另一半脑的时间（最多时间的那半脑）ans=ans+op;dp.clear();//记得将背包清空！}cout<<ans;return 0;
}