P6389 MUZICARI

MspAInt · 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