题解：P2608 [ZJOI2010] 任务安排

· · 题解

题意简述

两项任务分别包含 S_1,S_2 次串行操作。每次操作可以交给任意工人，同一工人不能同时工作。求两项任务完成时间之和的最小值。

解题思路

不能假设至多一名工人参与两项任务。不同工人可能在两条任务链之间交替，形成更优的流水安排。因此直接记录操作完成事件。

任意时刻，每项任务至多有一次操作正在执行。固定工人分配与每名工人的操作顺序后，将所有操作尽量左移，不会增加完成时间。于是存在最优方案，使每次操作都在时刻 0 或某次操作完成时开始。

若两项任务当前都空闲，只有以下选择：

第二种选择中，若第一项操作先完成，其工人在下一个事件前已经空闲。固定仍在执行第二项操作的工人 k 后，第一项操作仅需使用除 k 外最快的工人。第二项操作先完成时同理。

若第二项操作正由工人 k 执行到时刻 e，第一项任务在时刻 t 已经空闲，则有两类选择：

若新操作在 e 前完成，工人 x 的编号不会影响后续状态。选择除 k 外执行第一项操作最快的工人必然不劣。若新操作晚于 e 完成，工人 x 在下一个事件后仍被占用。此时其编号会影响后续决策，因此枚举所有 x。交换两项任务的角色后完全相同。

设 g_{i,j} 表示两项任务都空闲，且已经完成 i,j 次操作的最早时刻。此时所有工人都空闲，更晚的同类状态没有保留必要。再维护两类状态：

同一状态中的 (t_1,e_1) 若满足 t_1\le t_2 且 e_1\le e_2，则它不晚于 (t_2,e_2) 释放任何任务或工人。后一状态的任意后续安排都能由前一状态完成得不晚，因此只保留二维偏序下的极小二元组。

按已经完成的操作总数递增转移。每次转移至少完成一次操作，所以不会产生环。若一项任务已经完成，另一项任务在当前操作结束后始终交给对应操作最快的工人即可。

记单个状态保留的二元组数量上界为 K。时间复杂度为 O(S_1S_2N^2K^2)，空间复杂度为 O(S_1S_2NK)。本题中 S_1,S_2\le7，保留的偏序前沿很小。

正确性证明

固定一个可行安排的工人分配，以及每名工人的操作顺序。任务内部的顺序与工人的顺序共同构成一张有向无环图。按拓扑序令每次操作在所有前驱完成后立即开始，只会提前操作。每次操作的开始时刻均为 0 或某个前驱的完成时刻。因此存在具有该性质的最优安排。

考虑这样的安排在某个完成事件后的决策。若另一项操作仍由工人 k 执行，其他工人均空闲。空闲任务要么立即选择另一名工人，要么等到时刻 e。新操作若先完成，所选工人在下一个事件前已经释放。改用除 k 外更快的工人只会提前该事件，且不会减少后续可用工人。新操作若后完成，其工人编号仍影响下一步，算法逐一枚举。

两项任务都空闲时，至少有一项操作立即开始。若两项同时开始，对先完成的操作使用同样的替换。因此，算法的转移覆盖了下一个事件的所有可能。

对完成事件数归纳。初始状态 g_{0,0}=0 正确。假设算法已经包含某个最优规范安排的当前状态，前述分类保证其下一次决策对应至少一条转移。转移按实际完成顺序更新操作数、空闲时刻、运行工人与结束时刻，因此产生的状态仍与该安排一致。

若 (t_1,e_1) 支配 (t_2,e_2)，则可从前者按后者的绝对时刻复现后续安排。需要时主动等待即可。两项任务与工人 k 都不会更晚释放，其他工人的可用情况完全相同。因此复现后的任务完成时刻不会更晚，删除被支配的二元组不会丢失最优解。

归纳可知，算法覆盖至少一个最优安排。所有转移又都满足任务串行与工人互斥限制，计算出的每个答案均可实际执行。因此算法所得最小值就是 E_1+E_2 的最小值。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=105;
const int S=8;
const int inf=0x3f3f3f3f;
int n,s1,s2,mn1,mn2,ans;
int p[N],q[N],mn_p[N],mn_q[N],g[S][S];
vector<pii> f[2][S][S][N];
void add(vector<pii> &v,int x,int y)
{
    for(auto [a,b]:v)if(a<=x&&b<=y)return;
    auto it=v.begin();
    for(auto [a,b]:v)if(x>a||y>b)*it++={a,b};
    v.erase(it,v.end());
    v.push_back({x,y});
}
void upd(int i,int j,int t)
{
    if(i==s1&&j==s2)ans=min(ans,2*t);
    else if(i==s1)ans=min(ans,2*t+(s2-j)*mn2);
    else if(j==s2)ans=min(ans,2*t+(s1-i)*mn1);
    else g[i][j]=min(g[i][j],t);
}
void calc(int a,int b)
{
    if(g[a][b]<inf&&a<s1&&b<s2)
    {
        int t=g[a][b];
        upd(a+1,b,t+mn1);
        upd(a,b+1,t+mn2);
        for(int i=1;i<=n;i++)
        {
            if(mn_p[i]<q[i])
            {
                int x=t+mn_p[i],y=t+q[i];
                if(a+1==s1)ans=min(ans,x+y+(s2-b-1)*mn2);
                else add(f[0][a+1][b][i],x,y);
            }
            else if(mn_p[i]==q[i])upd(a+1,b+1,t+q[i]);
            if(mn_q[i]<p[i])
            {
                int x=t+mn_q[i],y=t+p[i];
                if(b+1==s2)ans=min(ans,x+y+(s1-a-1)*mn1);
                else add(f[1][a][b+1][i],x,y);
            }
            else if(mn_q[i]==p[i])upd(a+1,b+1,t+p[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(auto [t,e]:f[0][a][b][i])
        {
            upd(a,b+1,e);
            int x=t+mn_p[i];
            if(x<e)
            {
                if(a+1==s1)ans=min(ans,x+e+(s2-b-1)*mn2);
                else add(f[0][a+1][b][i],x,e);
            }
            else if(x==e)upd(a+1,b+1,e);
            for(int j=1;j<=n;j++)
            {
                if(i==j)continue;
                x=t+p[j];
                if(x<=e)continue;
                if(b+1==s2)ans=min(ans,e+x+(s1-a-1)*mn1);
                else add(f[1][a][b+1][j],e,x);
            }
        }
        for(auto [t,e]:f[1][a][b][i])
        {
            upd(a+1,b,e);
            int x=t+mn_q[i];
            if(x<e)
            {
                if(b+1==s2)ans=min(ans,x+e+(s1-a-1)*mn1);
                else add(f[1][a][b+1][i],x,e);
            }
            else if(x==e)upd(a+1,b+1,e);
            for(int j=1;j<=n;j++)
            {
                if(i==j)continue;
                x=t+q[j];
                if(x<=e)continue;
                if(a+1==s1)ans=min(ans,e+x+(s2-b-1)*mn2);
                else add(f[0][a+1][b][j],e,x);
            }
        }
    }
}
void solve()
{
    cin>>n>>s1>>s2;
    for(int i=1;i<=n;i++)cin>>p[i]>>q[i];
    mn1=*min_element(p+1,p+n+1);
    mn2=*min_element(q+1,q+n+1);
    for(int i=1;i<=n;i++)
    {
        mn_p[i]=mn_q[i]=inf;
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            mn_p[i]=min(mn_p[i],p[j]);
            mn_q[i]=min(mn_q[i],q[j]);
        }
    }
    memset(g,0x3f,sizeof g);
    for(int i=0;i<=s1;i++)
    {
        for(int j=0;j<=s2;j++)
        {
            for(int k=1;k<=n;k++)
            {
                f[0][i][j][k].clear();
                f[1][i][j][k].clear();
            }
        }
    }
    ans=inf;
    g[0][0]=0;
    for(int i=0;i<=s1+s2;i++)
    {
        for(int j=max(0,i-s2);j<=min(s1,i);j++)
        {
            calc(j,i-j);
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}