四边形不等式

参考资料

• 四边形不等式 - OI Wiki

简介

若代价函数 $w$ 满足 四边形不等式：对 $a\le b\le c\le d$ 有 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，则相应 DP 的最优决策点具有单调性。利用决策单调性，可把区间 DP 由 $O(n^3)$ 优化到 $O(n^2)$，把一类一维 DP 优化到 $O(n\log n)$。

例题

洛谷 P4767 [IOI 2000] 邮局 加强版

数轴上有 $n$ 个村庄，要建 $m$ 个邮局，使每个村庄到最近邮局的距离之和最小，求该最小值。