[CF797F] Mice and Holes

不难发现一个性质，如果某个方案中老鼠 $i,j$ 分别躲进了洞 $u,v$ 中，$x_i<x_j$ 而 $p_u>p_v$，显然调整为让 $i$ 躲进 $v$，$j$ 躲进 $u$，该方案一定不会变劣。因此，将老鼠按照起点所在的位置划分为几个连续段，这些连续段从左往右依次匹配从左往右的洞，一定不劣。

考虑朴素 DP，设 $f_{i,j}$ 表示前 $i$ 个洞匹配前 $j$ 个老鼠，老鼠需要走的总长度最小值。有

$$\displaylines{\begin{aligned} f_{i,j}&=\min_{k=j-c_i}^j\left\{f_{i-1,k}+\sum_{k<t\le j}|x_t-p_i|\right\}\\ &=\min_{k=j-c_i}^j\{f_{i-1,k}+s_{i,j}-s_{i,k}\}\\ &=s_{i,j}+\min_{k=j-c_i}^j\{f_{i-1,k}-s_{i,k}\} \end{aligned} }$$

其中 $s_{i,j}$ 表示 $\sum_{t\le j}|x_t-p_i|$，并且 $j$ 增大的过程中，$k$ 的合法取值区间单调右移，使用优先队列优化到 $O(nm)$。