P4767 [IOI 2000] 邮局 加强版

本题是四边形不等式的应用。

题目描述

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标 $X_i$ 标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

第一行包含两个整数：第一个是村庄 $V$ 的数量，第二个是邮局的数量 $P$。

第二行包含 $V$ 个整数。这些整数是村庄的位置。

输出格式

第一行包含一个整数 $S$，它是每个村庄与其最近的邮局之间的所有距离的总和。

输入输出样例 #1

输入 #1

10 5 
1 2 3 6 7 9 11 22 44 50

输出 #1

9

说明/提示

对于 $40\mathrm{\%}$ 的数据，$V\le 300$。

对于 $100\mathrm{\%}$ 的数据，$1\le P\le 300$，$P\le V\le 3000$，$1\le X_i\le 10000$。

题解

状态定义和转移

定义 $f(i,j)$ 表示将前 $i$ 个村庄中划分成 $j$ 段，每段中点分配一个邮局方案下的最小距离总和。显然有

$$f(i,j)=\underset{0\le k<i}{min}\{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(P{V}^2)$ 的算法，可以得到 $40\mathrm{\%}$ 的分数。

四边形不等式优化

很容易证明 $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)$。