自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

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

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

以下是正文

前情提要

数据过水导致错误 dp 只会 WA 两个点差评。

问题是我一来就认为那个错误做法很假随便 Hack 就没写。

这样的情况下还能上榜？

$833$ 分第 $10$ 名！

不过我本来就切不了这道题，因为我没想清楚，赛后还调试了两个小时才过。

设置状态

将 $A$ 存在数组 $a$ 中，$B$ 存在数组 $b$ 中，分别排序，设长度为 $n,m$。

容易发现同一时刻走过的火车形如 $a,b$ 中的前缀。

设 $f_{x,y}$ 表示 $a$ 中走了前 $x$ 个，$b$ 中走了前 $y$ 个，最后一次走 $A$ 这一边，出发时间为 $a_x$，之后要全部走完还需要的答案。

$g_{x,y}$ 即最后一次走 $B$ 这一边，出发时间为 $b_x$。

转移式很简单：$f_{x,y}\leftarrow f_{x+1,y}$，如果 $b_{y+1}\ge a_x+T$，可以 $f_{x,y}\leftarrow g_{x,y+1}$，$g$ 的转移同理。

其他转移

上面写了 $f_{x,y}\leftarrow g_{x,y+1}$ 是有条件的！

如果 $b_{y+1}<a_x+T$，下一步又想要走 $b$，该怎么办？

考虑这时会出现一次行走的末尾没有任何列车达到极限，不属于之前的任何一种状态。

发现这种情况一定形如两边交替只走 $T$ 的时间，最多不会超过 $n$ 次，所以枚举进行了多少次可以在 $O(n)$ 的时间内得出答案：

ll sol(int tg,int x,int y,ll t){
    if(x>n||y>m)return 1e18;
    ll res=8e18,sum=0;
    while(1){
        if(x==n&&y==m){
            res=min(res,sum);
            break;
        }
        if(tg){// x ran.
            while(x<n&&a[x+1]<t)sum+=t-a[++x];
            if(x<n)res=min(res,sum+f[x+1][y]);
            if(y==m){
                if(x==n)res=min(res,sum);
                break;
            }
            if(b[y+1]>=t+K){
                res=min(res,sum+g[x][y+1]);
                break;
            }else tg=0,t+=K;
        }else{
            while(y<m&&b[y+1]<t)sum+=t-b[++y];
            if(y<m)res=min(res,sum+g[x][y+1]);
            if(x==n){
                if(y==m)res=min(res,sum);
                break;
            }if(a[x+1]>=t+K){
                res=min(res,sum+f[x+1][y]);
                break;
            }else tg=1,t+=K;
        }
    }
    return res;
}

直接调用这个函数会达到 $O(n^3)$，不能通过。

但你会发现对于每一个 $x$ 都会是同一种状态，因为这时第一步 $b$ 都会走到最后一个 $b_y\le a_x+k$ 的位置，于是对于 $x$ 记忆化即可，$g$ 的转移同理。

于是做完了，时空复杂度 $O(n^2)$：

cin>>T>>K;
while(T--){
    cin>>s;
    if(s[0]=='A')cin>>a[++n];
    else cin>>b[++m];
}
a[++n]=0,b[++m]=0;
sort(a+1,a+n+1),sort(b+1,b+m+1);
for(i=1;i<=n;++i)A[i]=A[i-1]+a[i];
for(i=1;i<=m;++i)B[i]=B[i-1]+b[i];
for(i=0;i<=n+1;++i)
    for(j=0;j<=m+1;++j)
        f[i][j]=g[i][j]=3e18;
for(x=1;x<=n;++x){
    for(k=1;k<=m&&b[k]<a[x]+K;++k);
    tx[x]=k;
}
for(x=1;x<=m;++x){
    for(k=1;k<=n&&a[k]<b[x]+K;++k);
    ty[x]=k;
}
for(x=n;x;--x)
    for(y=m;y;--y){
        if(x==n&&y==m){
            f[x][y]=g[x][y]=0;
            continue;
        }
        f[x][y]=f[x+1][y];
        if(y==tx[x]-1){
            vf[x]=min(sol(0,x,tx[x]-1,a[x]+K),g[x][tx[x]]);
            // cln<<x<<" "<<tx[x]<<" "<<vf[x]<<endl;
        }
        if(x==ty[y]-1)vg[y]=min(sol(1,ty[y]-1,y,b[y]+K),f[ty[y]][y]);
        if(b[y+1]>=a[x]+K)f[x][y]=min(f[x][y],g[x][y+1]);
        else{
            v1=(a[x]+K)*(tx[x]-1-y)-(B[tx[x]-1]-B[y]);
            // cln<<(B[tx[x]-1]-B[y-1])<<endl;
            // cln<<x<<" "<<y<<" "<<v1<<endl;
            f[x][y]=min(f[x][y],vf[x]+v1);
        }
        g[x][y]=g[x][y+1];
        if(a[x+1]>=b[y]+K)g[x][y]=min(g[x][y],f[x+1][y]);
        else{
            v1=(b[y]+K)*(ty[y]-1-x)-(A[ty[y]-1]-A[x]);
            g[x][y]=min(g[x][y],vg[y]+v1);
            // cln<<(b[y]+K)*(ty[y]-1-x)<<endl;
            // cln<<y<<" "<<ty[y]<<" "<<vg[y]<<endl;
        }
        // cln<<x<<" "<<y<<" "<<f[x][y]<<" "<<g[x][y]<<endl;
    }
ll ans=min(f[1][1],g[1][1]);
printf("%lld\n",ans);