dp80求助
查看原帖
dp80求助
209758
AdGats楼主2021/1/25 09:39
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
bool dp[N];
int s[5],n[105],ans;
int main(){
	for(int i=1;i<=4;i++) cin>>s[i];
	for(int k=1;k<=4;k++){
		int sum=0;
		memset(n,0,sizeof(n));
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(int i=1;i<=s[k];i++) cin>>n[i],sum+=n[i],dp[sum]=1;
		int mid=(sum+1)/2;
		for(int i=1;i<=s[k];i++)
			for(int j=sum;j>=n[i];j--) dp[j]=dp[j]|dp[j-n[i]];
		//for(int i=1;i<=sum;i++) cout<<dp[i];
		for(int i=mid;i<=sum;i++) if(dp[i]){
			ans+=i;
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

2021/1/25 09:39
加载中...