P4767 [IOI2000] 邮局 加强版 题解 / 四边形不等式优化 DP 学习笔记
P4767 [IOI2000] 邮局 加强版
题目考察：四边形不等式优化动态规划。
题目简述：
在一条线上有
形式化题意：
给你
数据范围：
-
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\vee j=0\\+\infty&(i=0\vee j\ne 0)\wedge(i\ne 0\vee 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 个村庄中建邮局选中点最合适： -
选第 $\displaystyle\lfloor\frac{i+j}{2}\rfloor$ 个村庄建邮局是最优的，因为往右边建会使 $\displaystyle i\sim \lfloor\frac{i+j}{2}\rfloor$ 这些村庄去那里的距离加 $1$，剩下的会减 $1$，距离和会变大。 -
同上，第 $\displaystyle\lfloor\frac{i+j}{2}\rfloor$ 个村庄和第 $\displaystyle\lceil\frac{i+j}{2}\rceil$ 个村庄的距离和都是最小的。
综上，选第
这样时间复杂度是
我们发现求
这样时间复杂度是
正题开始
有一种 dp 叫四边形不等式优化动态规划。
证明
- 四边形不等式的定义：
设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} ，则能推出其满足四边形不等式。 - 证明
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} ，显然成立。
- 证明四边形不等式：
- 证明
f_{i,j} 满足四边形不等式：
因为f_{i,1}=w_{1,i} ，所以当j=1 时满足。
而后面f_{k,2}=f_{i,1}+w_{i+1,k} ，由于f_{k,2} 是由两个满足四边形不等式的函数相加得到的，所以他必然也满足四边形不等式，其实是我又懒了。
以此类推。 - 证明决策单调性（
d_{i,j-1}\le d_{i,j}\le d_{i+1,j} ）：
我又懒了，感性理解就是建的邮局少了，最后的邮局就要往前建；距离远了，最后的邮局就要往后建。（不然就与最优矛盾了） - 时间复杂度：
$i=2$ 时，$k\in[d_{2,2},d_{3,3}]$。 ...... 长度累加等于 $p_{m+1,m}-p_{1,1}+n<2n-2 故时间复杂度为
\Theta(n(n+m)) 。
代码