洛谷 P2392. kkksc03考前临时抱佛脚
原题链接
中等
作者:
Aqiw
,
2025-04-17 22:48:59
· 河北
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1020;
int dp[N][N];
int len[4];
int s[N];
signed main()
{
for(int i=0;i<4;i++) cin>>len[i];
int ans=0;
for(int i=0;i<4;i++)
{
int sum=0;
for(int j=1;j<=len[i];j++)
{
cin>>s[j];
sum+=s[j];
}
int res=0;
for(int j=1;j<=len[i];j++)
{
for(int k=0;k<=sum/2;k++)
{
dp[j][k]=dp[j-1][k];
if(k>=s[j]) dp[j][k]=max(dp[j][k],dp[j-1][k-s[j]]+s[j]);
res=max(res,dp[j][k]);
}
}
res=max(res,sum-res);
ans+=res;
}
cout<<ans<<endl;
return 0;
}