# 直线上的服务站：以最右服务站为状态

这是出题人的端点选址动态规划，由 [alternative.cpp](alternative.cpp) 实现，支持全部数据。先将房屋坐标排序为 $x_1\le\cdots\le x_N$ .每个连续服务组可在其中位数建站，因此只考虑在房屋处建站不会失去最优解。

## 两站之间的代价

当相邻的两个站位于 $x_i,x_j$ 时，中间房屋的贡献是

$$W(i,j)=\sum_{i<k<j}\min(x_k-x_i,x_j-x_k).$$

对固定 $i$ ，递增枚举 $j$ ，维护最后一个更接近左站或与两站等距的下标 $s$ ，初始 $s=i$ .当 $s+1<j$ 且 $x_{s+1}-x_i\le x_j-x_{s+1}$ 时增加 $s$ .用坐标前缀和 $P$ 得到

$$W(i,j)=P_s-P_i-x_i(s-i)+x_j(j-s-1)-(P_{j-1}-P_s).$$

分界只向右移动，全部 $W$ 可在 $O(N^2)$ 时间和空间内求出。

## 状态与转移

令 $F_t(j)$ 为设置 $t$ 个站、最右站位于房屋 $j$ 时，所有编号不大于 $j$ 的房屋的最小距离和。站的房屋下标严格递增，坐标允许相同。

$$F_1(j)=x_j(j-1)-P_{j-1},\qquad F_t(j)=\min_{t-1\le i<j}\{F_{t-1}(i)+W(i,j)\}.$$

相邻站之间的房屋只会选择这两个站之一，最左站左侧和最右站右侧分别全部选择该端站。因此，转移精确拼接了已处理的左侧和新增站间区间；最终答案是

$$\min_{M\le j\le N}\{F_M(j)+P_N-P_j-x_j(N-j)\}.$$

## 为什么可以分治优化

对 $i\le j\le k\le l$ ，有 $W(i,k)+W(j,l)\le W(i,l)+W(j,k)$ .可逐个房屋比较：位于中间 $[j,k]$ 的房屋，对应距离 $A\ge B$ 、$C\le D$ ，满足

$$\min(A,C)+\min(B,D)\le\min(A,D)+\min(B,C).$$

位于外侧 $[i,j]$ 或 $[k,l]$ 的房屋则直接使用“把可选的端站移远不会降低距离”的单调性。端点贡献为零，重复坐标同样成立。把所有房屋的贡献相加得到不等式。

于是固定 $t$ 时，最小编号的最优前驱随 $j$ 不减。计算目标区间中点的最优前驱后，可用它限制左右两半的搜索区间，每层动态规划耗时 $O(N\log N)$ .程序只依赖同一层的这个单调性。两层滚动数组保存 $F$ ，用 64 位距离和及足够大的正无穷。

总时间 $O(N^2+MN\log N)$ ，空间 $O(N^2)$ .该状态直接分解相邻设施间的服务代价；[中位数分组法](solution.zh.md)用常数时间区间公式节省二次空间，作为首选。两个算法均通过全部正式数据。方法归出题人，GPT-6 补齐证明与安全实现；实测见[性能记录](../../../docs/benchmark-R25.json)。