自动搬运

查看原文

来自洛谷，原作者为

	hmh13951417981 这个蒟蒻很懒，什么都没留下

搬运于2025-08-24 21:37:11，当前版本为作者最后更新于2019-04-03 11:32:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心题:既然是算较短的时间，如果左脑所用时间少就加在左脑，如果右脑所用时间少就加在右脑

#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,sum1,sum2,t,homework;
int main(){
    for(i=1;i<=4;i++)
        cin>>a[i];//输入
    for(i=1;i<=4;i++){
    sum1=sum2=0;//两边脑子时间清零
    for(j=1;j<=a[i];j++)
        {cin>>homework;
        if(sum1<=sum2) sum1+=homework;
        else sum2+=homework;}//哪边时间短就加在哪边
        t+=max(sum1,sum2);//取较长时间累加
    }cout<<t;//输出
    return 0;
}

满怀期待的提交后，结果有点震惊 结果

果然，贪心不是正解

后来思考了一下，便感觉是dp，对于一道题只有两个状态，一是加到左脑，二是加到右脑，所以是01背包

这里还可以用另一个思想，将一边的脑子加到最接近一半则另一边脑子时间就是正解

#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
int main(){
	for(i=1;i<=4;i++)
		cin>>a[i];
	for(i=1;i<=4;i++){
		sum=0;	
		for(j=1;j<=a[i];j++)
			{cin>>homework[j];//输入
			sum+=homework[j];}//总时间累加
		for(j=1;j<=a[i];j++)
			for(k=sum/2;k>=homework[j];k--)//只要是总和的一半
				dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);//01背包
		t+=sum-dp[sum/2];//累加为另一个脑子
		for(j=1;j<=sum/2;j++)
		dp[j]=0;//清零
	}
	cout<<t;//输出
	return 0;
}