题解

思路推导

把所有有人椅子的位置依次记为 $p_1,p_2,\ldots,p_k$，把所有空椅子的位置依次记为 $z_1,z_2,\ldots,z_m$。题目保证 $k\le m$。

任意最优匹配都可以调整为不交叉匹配。若 $p_x<p_y$ 却分别匹配到 $z_v<z_u$，由绝对值距离在直线上的单调性质，有

$$|p_x-z_u|+|p_y-z_v|\ge |p_x-z_v|+|p_y-z_u|.$$

因此交换这两个人的目标不会增大代价。反复消除交叉后，人的相对次序与所选空椅子的相对次序一致。

做法

依次扫描空椅子。令 $dp_j$ 表示已经考虑过当前前缀的空椅子，并让前 $j$ 个人就座的最小代价。初始时 $dp_0=0$，其余状态为无穷大。

扫描到空椅子 $z$ 时，倒序枚举 $j$。可以不使用这把椅子；也可以让第 $j$ 个人坐到这里，用

$$dp_j\leftarrow\min\bigl(dp_j,dp_{j-1}+|p_j-z|\bigr)$$

更新。倒序枚举保证每把空椅子只被使用一次。全部空椅子处理完后，$dp_k$ 即为答案。

正确性证明

由不交叉性质，至少存在一种最优方案，使第 $j$ 个人匹配到所选空椅子序列中的第 $j$ 个。因此只需在所有空椅子的有序子序列中选择长度为 $k$ 的一个。

扫描某把空椅子时，任一合法选择只有两种情况：不选它，状态保持不变；选择它作为当前最后一个人的目标，则此前必须已经为前一个人选择完目标，转移代价为两位置之差。转移完整覆盖且只覆盖所有有序子序列。归纳可知每个状态保存对应前缀内的最小代价，最终 $dp_k$ 就是全局最优值。

复杂度分析

设有人椅子数为 $k$。时间复杂度为 $O(nk)$，最坏为 $O(n^2)$；空间复杂度为 $O(k)$。