点的移动：题解

思路

若一个区间初始时已包含某个点，它不需要任何代价，可以删除。若区间 $A$ 包含区间 $B$，访问 $B$ 的移动轨迹必然也访问 $A$，所以 $A$ 也可以删除。把点排序，并按左端点降序、右端点升序扫描区间，维护已保留区间的最小右端点，即可在线性扫描中删除所有包含其他区间的区间。剩余区间按左右端点都是递增的。

剩余的每个区间一定处于某两个相邻点之间，或位于所有点的左侧、右侧。两个相邻点之间的一组区间只能由这两个点访问；由于区间两端同序，最优分配必然是一个前缀交给左点，剩余后缀交给右点。

若一个点为了访问其左侧区间需要向左走最远距离 $x$，为了访问右侧区间需要向右走最远距离 $y$，最小移动代价为

定义 $dp_i[j]$ 为处理完前 $i+1$ 个点，并把点 $i$ 与点 $i+1$ 之间区间的前 $j$ 个分给点 $i$ 时的最小代价。

做法

子任务 1 枚举每个尚未访问区间由哪个点负责。确定分配后，对每个点分别求最远左、右距离并计算路线代价。复杂度为 $O(n^m(n+m))$。

子任务 2 使用上述动态规划直接枚举相邻两层状态。若相邻组分别有 $x,y$ 个区间，转移复杂度为 $O(xy)$，总复杂度不超过 $O(m^2)$。

满分做法优化转移。固定当前点的右行距离 $y$，左行距离 $x$ 随上一层状态单调递减。把状态分成 $x>y$ 与 $x\le y$ 两段：

• $x>y$ 时，新增代价为 $x+2y$；
• $x\le y$ 时，新增代价为 $2x+y$。

分别预处理 $dp-r$ 的前缀最小值和 $dp-2r$ 的后缀最小值，再用双指针维护两段分界，即可让每个状态 $O(1)$ 转移。所有组的状态总数为 $O(m)$。

复杂度

排序复杂度为 $O((n+m)\log(n+m))$，动态规划复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。