用01背包,RE
查看原帖
用01背包,RE
270472
chensirui楼主2020/4/28 09:59

我**(口吐芬芳)

#include<bits/stdc++.h>
using namespace std;
int a[21],b[21],c[21],d[21],dp[601];
int cnt=0;
int s1,s2,s3,s4; 
int main()
{
    cin>>s1>>s2>>s3>>s4;
    int t,s;
    for(int i=1;i<=s1;i++)
    {
    	cin>>a[i];
    	s+=a[i];
	}
	for(int i=0;i<s1;i++)
	{
		for(int j=t/2;j>0;j--)
		{
			if(j>=a[i])
			    dp[j]=max(dp[j],dp[j-a[i]]-a[i]);
		}
	}
	cnt+=s-dp[t/2];
	memset(dp,0,sizeof(dp));
	s=0;
	for(int i=1;i<=s2;i++)
    {
    	cin>>b[i];
    	s+=b[i];
	}
	for(int i=0;i<s2;i++)
	{
		for(int j=t/2;j>0;j--)
		{
			if(j>=b[i])
			    dp[j]=max(dp[j],dp[j-b[i]]-b[i]);
		}
	}
	cnt+=s-dp[t/2];
	s=0;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=s3;i++)
    {
    	cin>>c[i];
    	s+=c[i];
	}
	for(int i=0;i<s3;i++)
	{
		for(int j=t/2;j>0;j--)
		{
			if(j>=c[i])
			    dp[j]=max(dp[j],dp[j-c[i]]-c[i]);
		}
	}
	cnt+=s-dp[t/2];
	memset(dp,0,sizeof(dp));
	s=0;
	for(int i=1;i<=s4;i++)
    {
    	cin>>d[i];
    	s+=d[i];
	}
	for(int i=0;i<s4;i++)
	{
		for(int j=s/2;j>0;j--)
		{
			if(j>=d[i])
			    dp[j]=max(dp[j],dp[j-d[i]]-d[i]);
		}
	}
	cnt+=s-dp[s/2];
	s=0;
	cout<<cnt;
	return 0;
}
2020/4/28 09:59
加载中...