题解：P11986 [JOIST 2025] 救护车 / Ambulance

· · 题解

四个医院还是太复杂了，于是先弱化一下问题，将 4 个医院变成 2 个，且两个医院处于对角线。

设第 i 个人到医院 (1,1) 的代价为 a_i，到医院 (L,L) 的代价为 b_i。可以发现 a_i+b_i 为一个定值，于是就是一个经典贪心，直接按照 a_i 排序后，前缀分配给医院 1，后缀分配给医院 2。

扩展到四个医院，还是按照刚刚的对角线划分。我们这次引入两个对角线序列，(1,1) 和 (L,L) 一组，(L,1) 和 (1,L) 一组。对于第一组按照到 (1,1) 的距离排序，对于第二组按照到 (1,L) 的距离排序。

枚举两个序列中的前后缀分界点，可以将所有点分成四组，每一组中的点可以前往两个地点。于是我们直接设计一个 dp，设 dp_{i,t} 表示考虑了这一组的中的前 i 个元素，第一个医院用时为 t 的时候，第二个医院的最小用时。对于四组分别 dp 之后，枚举 (1,1) 的用时，然后利用第一组和第二组的 dp 信息可以得到到 (1,L) 和到 (L,1) 的最小用时，利用第三组的 dp 信息可以得到 (L,L) 的最小用时，再利用第四组的 dp 信息判定 (L,L) 和 (L,1) 当前的用时是否合法即可。

单次 dp 是 O(nT) 的，如果直接枚举分界点就是 O(n^3T) 的。可以对于第一个分界点扫描线，维护下标为第二个分界点的前后缀 dp 值，这样子就可以做到 O(n^2T) 了。

洛谷有点卡常，你开局就特判一下肯定无解的情况可以冲过去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=170;
const int inf=1e9;
const int maxt=2e4+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
struct node{ int x,y; }a[maxn]; int to[maxn];
int L,n,T,p[maxn],q[maxn],dp[4][maxn][maxt];
int c1(int id){ return a[id].x+a[id].y-2; }
int c2(int id){ return a[id].x-1+L-a[id].y; }
int c3(int id){ return L-a[id].x+a[id].y-1; }
int c4(int id){ return L-a[id].x+L-a[id].y; }
bool cmp(int x,int y){ return c1(x)<c1(y); }
bool cmp2(int x,int y){ return c2(x)<c2(y); }
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>L>>n>>T; T/=2; bool flag=1; int co=T;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        cmin(co,c1(i)); cmin(co,c2(i));
        cmin(co,c3(i)); cmin(co,c4(i));
        flag&=(a[i].x==a[1].x&&a[i].y==a[1].y);
    }
    if(n/4*co>T){ cout<<"No"; return 0; }
    for(int i=1;i<=n;i++) p[i]=i,q[i]=i,to[i]=4; 
    sort(p+1,p+1+n,cmp); sort(q+1,q+1+n,cmp2);
    for(int i=0;i<=n;i++){//[1,i]->1  [i+1,n]->4
        //[1,j]->2 [j+1,n]->3
        for(int j=1;j<=n;j++){
            int u=q[j];
            for(int t=0;t<=T;t++){
                if(to[u]==1){
                    dp[2][j][t]=dp[2][j-1][t];
                    dp[0][j][t]=dp[0][j-1][t]+c2(u);
                    if(c1(u)<=t) cmin(dp[0][j][t],dp[0][j-1][t-c1(u)]);
                    if(t) cmin(dp[0][j][t],dp[0][j][t-1]);
                }else{
                    dp[0][j][t]=dp[0][j-1][t];
                    dp[2][j][t]=dp[2][j-1][t]+c2(u);
                    if(c4(u)<=t) cmin(dp[2][j][t],dp[2][j-1][t-c4(u)]);
                    if(t) cmin(dp[2][j][t],dp[2][j][t-1]);
                }
            }
        }
        for(int j=n-1;j>=0;j--){
            int u=q[j+1];
            for(int t=0;t<=T;t++){
                if(to[u]==1){
                    dp[3][j][t]=dp[3][j+1][t];
                    dp[1][j][t]=dp[1][j+1][t]+c3(u);
                    if(c1(u)<=t) cmin(dp[1][j][t],dp[1][j+1][t-c1(u)]);
                    if(t) cmin(dp[1][j][t],dp[1][j][t-1]);
                }else{
                    dp[1][j][t]=dp[1][j+1][t];
                    dp[3][j][t]=dp[3][j+1][t]+c3(u);
                    if(c4(u)<=t) cmin(dp[3][j][t],dp[3][j+1][t-c4(u)]);
                    if(t) cmin(dp[3][j][t],dp[3][j][t-1]);
                }
            }
        }
        for(int j=0;j<=n;j++){
            int z=T;
            for(int t1=0;t1<=T;t1++){//枚举 (1,1) 
                int t2=dp[0][j][t1],t3=dp[1][j][T-t1];
                if(max(t2,t3)>T) continue;
                t2=T-t2; t3=T-t3;
                if(dp[2][j][z]>t2) continue;
                while(z&&dp[2][j][z-1]<=t2) z--;
                if(dp[3][j][T-z]<=t3){ cout<<"Yes"; return 0; }
            }
        }
        to[p[i+1]]=1;
    }
    cout<<"No";
    return 0;
}