自动搬运

查看原文

来自洛谷，原作者为

	MspAInt **

搬运于2025-08-24 22:20:20，当前版本为作者最后更新于2023-04-13 13:23:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

装箱问题加强版。

题面貌似有问题，应该要求所有乐师的开始休息时刻之和最小？

将乐师的休息时长视为物品重量，那么我们要把“箱子”尽量装满。

因为同一时刻只能有两个乐师休息，所以有两个箱子。先考虑一个箱子，$dp_i$ 表示总共最多休息 $i$ 分钟的情况下，允许某些乐师休息的最长时间和。

易得方程：dp[i]=max(dp[i],dp[i-a[i]]+a[i])，显然一个乐师休息完紧接着下一个休息是最优的。

开一个 vector 记录转移过程，然后求一下每个休息完的乐师开始休息的时间。

不被包含在第一个箱子的最优解里的乐师要放到第二个箱子。此时只能一个接一个直接休息。

Code：

#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
const int N=5e2+10,M=5e3+10;
int n,m,a[N],dp[M],res[N],tim;
vector<int>e[M];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	memset(res,0x3f,sizeof(res));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=m;j>=a[i];j--)
			if(dp[j]<dp[j-a[i]]+a[i]){
				dp[j]=dp[j-a[i]]+a[i];
				e[j]=e[j-a[i]];e[j].push_back(i);
			}
	for(int i=0;i<e[m].size();i++){
		res[e[m][i]]=tim;
		tim+=a[e[m][i]];
	}tim=0;
	for(int i=1;i<=n;i++){
		if(res[i]>inf)res[i]=tim,tim+=a[i];
		printf("%d ",res[i]);
	}
    return 0;
}

record