一天 scx 回到家发现她公寓的走廊上有 $n$ 只老鼠，当然，她娇喘了一声，于是，受惊吓的老鼠们开始跑到走廊上的洞里。
走廊可以看作是一个一个数轴，上面有 $n$ 个老鼠和 $m$ 个洞，第 $i$ 个老鼠的坐标是 $x_i$，第 $j$ 个洞的坐标是 $p_j$，可以容纳 $c_j$ 个老鼠。
如果第 $i$ 个老鼠去洞 $j$，当然，它需要走 $|x_i - p_j|$ 的距离，求所有老鼠都到达某个洞最小距离和。
第一行包含两个正整数 $n, m$ ($n, m \leq 5000$)，分别表示老鼠和洞的数量。
第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$ ($-10^9 \leq x_i \leq 10^9$)，$x_i$ 表示第 $i$ 个老鼠的坐标。
接下来的 $m$ 行中，第 $j$ 行有两个正整数 $p_j, c_j$ ($-10^9 \leq p_j \leq 10^9, 1 \leq c_j \leq 5000$)，$p_j, c_j$ 分别表示第 $j$ 个洞的坐标和容量。
输入一行一个整数，代表最小距离和，如果不能使所有老鼠都到达洞，输出 -1。
显然先将老鼠的坐标和洞的坐标排序。故以下假设 $x_i \leq x_{i+1}$ 且 $p_j \leq p_{j+1}$。
记 $C_k = \sum\limits_{i=1}^k c_i$，$f_{i, j}$ ($0 \leq i \leq m, 0 \leq j \leq n$) 表示 (排序后) 对前 $i$ 个洞，前 $j$ 个老鼠均跑进洞中的最小距离和，当然，这只对 $0 \leq j \leq C_i$ 时才有定义，否则记 $f_{i, j} = +\infty$，根据定义有 $f_{i, 0} = 0$。
考虑转移，因为第 $i$ 个洞至多能容纳 $c_i$ 个老鼠，因此转移方程如下：
$$ f_{i, j} = \min_{j-c_i \leq k \leq j} \left\{ f_{i-1, k} + \sum_{l=k+1}^j |x_l - p_i| \right\} $$
记 $y_{i, j} = \sum\limits_{l=1}^j |x_l - p_i|$，即前 $j$ 个老鼠进第 $i$ 个洞的距离和，则
$$ f_{i, j} = \min_{j-c_i \leq k \leq j} \left\{ f_{i-1, k} + y_{i, j} - y_{i, k} \right\} = \min_{j-c_i \leq k \leq j} \left\{ f_{i-1, k} - y_{i, k} \right\} + y_{i, j} $$
最后答案是 $f_{m, n}$。可以看出，这是一个 $O(n^2 m)$ 的动态规划，然而取 $\min$ 的一些值是关于 $k$ 的单变量函数，故可以使用单调队列优化，最终时间复杂度 $O(nm)$。
(2019.6.3 更新：更进一步的分析见这里)
#include <bits/stdc++.h>
#define N 5122
#define INF 0x7f7f7f7f7f7f7f7fll
#define p first
#define c second
using namespace std;
typedef pair <int, int> pr;
typedef long long ll;
int n, m, h, t;
int i, j, k;
int x[N];
pr hole[N];
ll f[N][N], s[N];
int que[N];
int main(){
scanf("%d%d", &n, &m);
memset(f, 127, sizeof f); f[0][0] = 0;
for(i = 1; i <= n; i++) scanf("%d", x + i);
for(i = 1; i <= m; i++) scanf("%d%d", &hole[i].p, &hole[i].c);
sort(x + 1, x + (n + 1)); sort(hole + 1, hole + (m + 1));
for(i = 1; i <= m; i++) {hole[i].c += hole[i - 1].c; f[i][0] = 0;}
for(i = 1; i <= m; i++){
for(j = 1; j <= n; j++) s[j] = s[j - 1] + abs(x[j] - hole[i].p);
h = 0; t = 1; que[0] = 0;
for(j = 1; j <= hole[i].c && j <= n; j++){
k = j - hole[i].c + hole[i - 1].c;
for(; h < t && que[h] < k; ++h);
for(; h < t && f[i - 1][que[t - 1]] - s[que[t - 1]] >= f[i - 1][j] - s[j]; --t);
que[t++] = j; k = que[h];
f[i][j] = f[i - 1][k] - s[k] + s[j];
}
}
printf("%lld\n", f[m][n] < INF ? f[m][n] : -1);
return 0;
}
毕竟是单调队列，比斜率优化要好写多了 (虽然都差不多的)，有两个坑点：
坑1：由于洞的容量有限制，所以转移的时候取 $\min$ 的下标 $k$ 满足 $\max\{0, j-c_i\} \leq k \leq j$，而不是单纯的 $0 \leq k \leq j$。
坑2：可以经过简单的撕烤可以得到，这显然是要开 long long 的 (好像样例 $2$ 的答案已经爆 int 了)……