80分求助,两个点wa
查看原帖
80分求助,两个点wa
107354
flowerdance_043楼主2021/9/22 21:36
#include<bits/stdc++.h>  
#define ll long long
using namespace std;
const int N = 105,inf = 0x3f3f3f3f;
int s[N],sum[N];
int a[N][N];
int dp[N];

int main(){
	for(int i=0;i<4;i++)cin>>s[i];
	for(int i=0;i<4;i++){
		for(int j=1;j<=s[i];j++){
			cin>>a[i][j];
			sum[i]+=a[i][j];
		}
	}
	ll ans=0;
	for(int t=0;t<4;t++){
		memset(dp,-inf,sizeof(dp));
		dp[0]=0;
		for(int i=1;i<=s[t];i++){
			for(int j=sum[t];j>=0;j--){
				if(j>=a[t][i]) dp[j]=max(dp[j],dp[j-a[t][i]]+a[t][i]);
			}
		}
		for(int j=(sum[t]+1)/2;j<=sum[t];j++){
			if(dp[j]>=0){
				ans+=dp[j];
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
2021/9/22 21:36
加载中...