20分求助
查看原帖
20分求助
527772
Login_楼主2021/9/17 19:06
#include<iostream>
#include<algorithm>
#include<cstring>

using std::cin;
using std::cout;
using std::endl;
using std::max;
using std::memset;

int s[4];
int a[5];
int dp[25][1500];
int sum=0;
int maxx;

int main()
{
	for(int i=0;i<4;i++)
		cin>>s[i];
	for(int i=0;i<4;i++)
	{
		int sum_time=0;
		for(int j=0;j<s[i];j++)
		{
			cin>>a[j];
			sum_time+=a[j];
		}
		double w=1.0*sum_time/2;
		for(int j=a[0];j<=w;j++)	//初始化 
			dp[0][j]=a[0];
		for(int k=1;k<s[i];k++)		//核心
		{
			for(int j=0;j<=w;j++)
			{
				if(j<a[k]) dp[k][j]=dp[i-1][j];
				else dp[k][j]=max(dp[k-1][j],dp[k-1][j-a[k]]+a[k]);
				maxx=dp[k][j];
			}
			if(k==s[i]-1) sum+=(sum_time-maxx);
		}
		if(s[i]==1) sum+=a[0];
		memset(dp,0,sizeof(dp));
	}
	cout<<sum;
	return 0;
}
2021/9/17 19:06
加载中...