本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-18 21:11:36

P4767 [IOI2000] 邮局 加强版

题目考察：四边形不等式优化动态规划。
题目简述：
在一条线上有 $n$ 个村庄，现在要在 $m$ 个村庄上建邮局，使所有村庄到他们最近的邮局的距离之和最小，求距离和。
形式化题意：
给你 $\{a_n\}$，求：
$$\min_{1\le id_1<id_2<\dots<id_m\le n}(\sum_{i=1}^n \min_{j=1}^m(|a_i-a_{id_j}|))$$ 数据范围：

• $1\le n\le 3000$
• $1\le m\le 300$
• $m\le n$
• $\forall i\in[1,n],1\le a_i\le 10^4$

设状态 $f_{i,j}$ 为在前 $i$ 个村庄里已经建了 $j$ 个邮局的最小距离和，$w_{i,j}$ 为在第 $i$ 到 $j$ 个村庄中建一个邮局的最小距离和，转移方程为：
$$f_{i,j}=\begin{cases}0&i=0\ee j=0\+\infty&(i=0\ee j\ne 0)\wedge(i\ne 0\ee j=0)\\min_{k=1}^{i-1}(f_{k,j-1}+w_{k+1,i})&\text{otherwise}\end{cases}$$ $$w_{i,j}=\begin{cases}0&i=j\\sum_{k=i}^j|a_k-a_{\lfloor\frac{i+j}{2}\rfloor}|&i\ne j\end{cases}$$ 证明 $1$：在第 $i$ 个村庄和第 $j$ 个村庄中建邮局选中点最合适：

• $j-i+1$ 为奇数：
  选第 $\displaystyle\lfloor\frac{i+j}{2}\rfloor$ 个村庄建邮局是最优的，因为往右边建会使 $\displaystyle i\sim \lfloor\frac{i+j}{2}\rfloor$ 这些村庄去那里的距离加 $1$，剩下的会减 $1$，距离和会变大。
• $j-i+1$ 为偶数：
  同上，第 $\displaystyle\lfloor\frac{i+j}{2}\rfloor$ 个村庄和第 $\displaystyle\lceil\frac{i+j}{2}\rceil$ 个村庄的距离和都是最小的。

综上，选第 $\displaystyle\lfloor\frac{i+j}{2}\rfloor$ 个村庄是没有问题的。

这样时间复杂度是 $\Theta(n^2(n+m))$，T 飞了。

我们发现求 $w_{i,j}$ 可以用前缀和实现，我们将小于中点和大于中点的村庄分开讨论，设 $sum_i=\sum_{j=1}^ia_j$（当然要排序），式子就变成了：
$$w_{i,j}=|a_{\lfloor\frac{i+j}{2}\rfloor}\times(\lfloor\frac{i+j}{2}\rfloor-i)-(sum_{\lfloor\frac{i+j}{2}\rfloor-1}-sum_{i-1})|+|(sum_j-sum_{\lfloor\frac{i+j}{2}\rfloor})-a_{\lfloor\frac{i+j}{2}\rfloor}\times (j-\lfloor\frac{i+j}{2}\rfloor)|$$ 这样时间复杂度是 $\Theta(n^2m)$，又 T 飞了。

正题开始

有一种 dp 叫四边形不等式优化动态规划。
证明 $2$：证明四边形不等式优化动态规划的正确性和时间复杂度：

1. 四边形不等式的定义：
   设 $f_{x,y}$ 是一个函数，对于所有的 $a\le b\le c\le d$，都满足 $f_{a,d}+f_{b,c}\ge f_{a,c}+f_{b,d}$，则称其满足四边形不等式。
   特别地，若对于所有的 $i<j$，都有 $f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}$，则能推出其满足四边形不等式。
2. 证明 $w_{i,j}$ 满足四边形不等式和单调性：
   • 证明四边形不等式：
     证明 $w_{i,j+1}+w_{i+1,j}\ge w_{i,j}+w_{i+1,j+1}$，我们要分别分解。
     因为我懒，分解的式子就不写了，最终结果就是这样的： 注：图中省略了一些距离，但结果相同。
   • 证明单调性： 区间包含 $w_{i+1,j}\le w_{i,j+1}$，显然成立。
3. 证明 $f_{i,j}$ 满足四边形不等式：
   因为 $f_{i,1}=w_{1,i}$，所以当 $j=1$ 时满足。
   而后面 $f_{k,2}=f_{i,1}+w_{i+1,k}$，由于 $f_{k,2}$ 是由两个满足四边形不等式的函数相加得到的，所以他必然也满足四边形不等式，其实是我又懒了。
   以此类推。
4. 证明决策单调性（$d_{i,j-1}\le d_{i,j}\le d_{i+1,j}$）：
   我又懒了，感性理解就是建的邮局少了，最后的邮局就要往前建；距离远了，最后的邮局就要往后建。（不然就与最优矛盾了）
5. 时间复杂度：
   $i=1$ 时，$k\in[d_{1,1},d_{2,2}]$。
   $i=2$ 时，$k\in[d_{2,2},d_{3,3}]$。
   ......
   长度累加等于 $p_{m+1,m}-p_{1,1}+n<2n-2$ 故时间复杂度为 $\Theta(n(n+m))$。

代码