本题是四边形不等式的应用。
题目描述
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标 $X_i$ 标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
输入格式
第一行包含两个整数：第一个是村庄 $V$ 的数量，第二个是邮局的数量 $P$。
第二行包含 $V$ 个整数。这些整数是村庄的位置。
输出格式
第一行包含一个整数 $S$，它是每个村庄与其最近的邮局之间的所有距离的总和。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
对于 $40%$ 的数据，$V \leq 300$。
对于 $100%$ 的数据，$1 \leq P \leq 300$，$P \leq V \leq 3000$，$1 \leq X_i \leq 10000$。
题解
状态定义和转移
定义 $f(i,j)$ 表示将前 $i$ 个村庄中划分成 $j$ 段，每段中点分配一个邮局方案下的最小距离总和。显然有 $$ f(i,j) = \min_{0 \le k < i}\set{f(k,j-1) + w(k+1,i)} $$ 其中 $w(k+1,i)$ 表示将第 $k+1$ 个到第 $i$ 个村庄划分为一段，且分配一个邮局的最小距离总和。显然每段中把邮局放在中间村庄（奇数个村庄）或中间两个村庄之间（偶数个村庄）是距离总和最小的方案。不失一般化，对于 $[l,r]$ 这一段我们把邮局放在 $mid = \lfloor \frac{l+r}{2} \rfloor$ 总是最优的。
因此 $w(l,r)$ 可以预处理： $$ w(l,r) = w(l,r-1) + X_r - X_{mid} $$ 至此，我们获得了 $O(PV^2)$ 的算法，可以得到 $40%$ 的分数。
四边形不等式优化
很容易证明 $w(l,r)$ 满足四边形不等式。因此对于任意 $f(i,j)$ 的最优决策 $d(i,j) = k$，都有决策单调性： $$ d(i,j-1) \le d(i,j) \le d(i+1,j) $$ 其实上述决策单调性非常显然，不需要四边形不等式也能轻松证明。
$f(i,j)$ 状态转移时只要在 $d(i,j-1) \le k \le d(i+1,j)$ 范围内枚举即可。
时间复杂度 $O(PV)$。
