题解：P11986 [JOIST 2025] 救护车 / Ambulance
cuijiexiong · · 题解
我做这题时，没看懂别人的题解（我还是太菜了），搞了好久（2 天）才想出来，还是和同学讨论的情况下。还是自己写一篇题解好。
题目大意
有一个
解题思路
初步分析
由于救护车需要往返，我们先将
我们将四家医院编号如下：
- ① 位于
(1, 1) 。 - ② 位于
(1, L) 。 - ③ 位于
(L, 1) 。 - ④ 位于
(L, L) 。
四个医院的情况稍显复杂，我们先从两个医院的情况入手，以对角线上的 ① 和 ④ 为例。
一个病人可以选择去 ① 或 ④，所需时间分别为
可以证明这是不劣的：
假设有两个病人i 和j ，坐标分别为(x_i, y_i) 和(x_j, y_j) ，且i 去 ①，j 去 ④。若x_i + y_i - 2 > x_j + y_j - 2 ，
则可推出2L - x_i - y_i < 2L - x_j - y_j 。
基于这两个不等式，将j 分配去 ①，i 分配去 ④ 显然是更优的选择。
因此，我们只需枚举中间的分界点即可确定最优分配。
回到原问题，另一条对角线上的 ② 和 ③ 的分配也是类似的：按到 ② 的距离排序，去 ② 的病人是排序后的一个前缀，去 ③ 的是一个后缀。
考虑 DP
然而，上述分析仅考虑了同一对角线上的医院分配，未考虑病人是去 ①④ 还是去 ②③。
我们先将所有病人按到 ① 的距离排序，并枚举去 ① 和去 ④ 的分界点。这样我们将病人分为两部分：左边的病人可以去 ①、②、③，右边的病人可以去 ②、③、④。接着，我们将左边和右边的病人分别按到 ② 的距离排序。由于左右两部分处理方式类似，下面我们以左边为例进行说明。
排序后，我们枚举左边去 ② 和去 ③ 的分界点，将左边进一步分为两部分：左左半（可去 ①、②）和左右半（可去 ①、③）。下图展示了左左半、左右半、右左半、右右半的划分：
通过上述划分，我们将整个序列分成了四个部分。这四个部分的处理方式类似，这里我们以左左半为例进行讨论。
考虑使用动态规划（DP）。定义状态
其中
类似地，我们为其他三个部分也定义 DP 状态：
这些 DP 状态有什么用呢？题目只要求判断是否能在时间
- 枚举左左半去 ① 的总用时
t_1 。 - 计算
t_2 = f_{0,k_1,t_1} 和t_3 = g_{0,k_2,T - t_1} 。 - 计算
t_4 = f_{1,k_3,T - t_2} + g_{1,k_4,T - t_3} 。 - 若
t_4 \le T ，则输出Yes。
优化
我们来分析一下时间复杂度：
- 枚举四个部分的分界线：
O(n^3) 。 - 进行 DP 计算：
O(nT) 。
总时间复杂度为
回顾我们最初的分析：按到 ① 的距离排序后，去 ① 的病人一定是一个前缀；按到 ② 的距离排序后，去 ② 的病人也一定是一个前缀。而我们之前枚举四个部分的分界线时，并未保证去 ② 的病人是前缀，导致效率低下。具体优化方法如下图所示（~有点不想写了~）：
通过这种方式，我们将枚举分界线的时间复杂度降为
需要注意的是，DP 计算其实和四半的分界线无关，可以在枚举分界线之前预处理完成，就类似前缀后缀优化。
最终时间复杂度就为
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,Tx=2e4+100;
int L,n,T,coin;
int f[2][N][Tx],g[2][N][Tx];
struct node{
int x,y,id;
};
node a[N],b[N],ra[N];
// 计算病人X到医院op的用时
int to(node X,int op){
int x=X.x,y=X.y;
if(op==1) return x+y-2; // 到①医院的时间
if(op==2) return L-1+x-y; // 到②医院的时间
if(op==3) return L-1-x+y; // 到③医院的时间
if(op==4) return 2*L-x-y; // 到④医院的时间
}
// 按到①医院的距离排序
bool cmp1(node x,node y){
return to(x,1)<to(y,1);
}
// 按到②医院的距离排序，距离相同时按到①的距离排序
bool cmp2(node x,node y){
if(to(x,2)==to(y,2)) return to(x,1)<to(y,1);
return to(x,2)<to(y,2);
}
// DP预处理：tl到tr区间，To表示主要医院，is表示是否交换医院角色
void get_dp(int tl,int tr,int To,bool is){
sort(a+tl,a+1+tr,cmp2); // 对区间内病人按到②的距离排序
// 初始化DP数组
for(int i=0;i<=T;i++)
f[is][tl-1][i]=g[is][tr+1][i]=0;
// 前向DP：f[is][i][j]表示前i个病人，去主要医院总时间为j时，去次要医院的最小总时间
for(int i=tl;i<=tr;i++){
for(int j=0;j<=T;j++){
int x=to(a[i],To),y=to(a[i],2); // x去主要医院时间，y去次要医院时间
if(is) swap(x,y); // 如果is为真，交换医院角色
f[is][i][j]=f[is][i-1][j]+y; // 当前病人去次要医院
if(j>=x) f[is][i][j]=min(f[is][i][j],f[is][i-1][j-x]); // 当前病人去主要医院
}
}
// 后向DP：g[is][i][j]表示从i到tr的病人，去主要医院总时间为j时，去次要医院的最小总时间
for(int i=tr;i>=tl;i--){
for(int j=0;j<=T;j++){
int x=to(a[i],To),y=to(a[i],3); // x去主要医院时间，y去次要医院时间
if(is) swap(x,y); // 如果is为真，交换医院角色
g[is][i][j]=g[is][i+1][j]+y; // 当前病人去次要医院
if(j>=x) g[is][i][j]=min(g[is][i][j],g[is][i+1][j-x]); // 当前病人去主要医院
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>L>>n>>T;
T/=2; // 因为救护车需要往返，所以时间除以2
// 读入病人坐标并计算最小总时间（用于初步剪枝）
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
coin+=min(min(to(a[i],1),to(a[i],2)),min(to(a[i],3),to(a[i],4)));
}
// 如果最小总时间已经超过T，直接输出No
if(coin/4>T){
cout<<"No";
return 0;
}
// 按到①医院的距离排序
sort(a+1,a+1+n,cmp1);
// 建立按到②医院距离排序的映射
for(int i=1;i<=n;i++) b[i]=a[i],b[i].id=i;
sort(b+1,b+1+n,cmp2);
for(int i=1;i<=n;i++) a[b[i].id].id=i;
// 备份原始数组
for(int i=1;i<=n;i++)
ra[i]=a[i];
// 枚举去①和去④的分界点V
for(int V=0;V<=n;V++){
// 预处理左边区间[1,V]和右边区间[V+1,n]的DP
get_dp(1,V,1,0); // 左边：主要医院①，次要医院②
get_dp(V+1,n,4,1); // 右边：主要医院④，次要医院②（is=1表示交换角色）
// 枚举去②和去③的分界点U
for(int U=0,L=0,R=V;U<=n;U++){
// 维护左左半大小L和右左半大小R
if(L<V&&a[L+1].id<=U) L++;
if(R<n&&a[R+1].id<=U) R++;
// 枚举左左半去①的总时间t1
for(int t1=0;t1<=T;t1++){
int t2=f[0][L][t1]; // 左左半去②的最小总时间
int t3=g[0][L+1][T-t1]; // 左右半去③的最小总时间
if(t2>T||t3>T) continue; // 如果时间超限，跳过
// 计算右边去④的总时间
int t4=f[1][R][T-t2]+g[1][R+1][T-t3];
if(t4<=T){ // 如果所有时间都在限制内
cout<<"Yes";
return 0;
}
}
}
// 恢复原始数组，为下一次枚举做准备
for(int i=1;i<=n;i++)
a[i]=ra[i];
}
cout<<"No";
return 0;
}代码经 AI 注释，但其他都是我写的。~有点懒，不想写注释了。~
求管理员让过。