四边形不等式
我们称一个二元函数\(w(i, j)\)满足四边形不等式，当且仅当对于任意\(a \le b \le c \le d\)满足：
即交叉小于包含。
其可以用来对转移进行优化，具体的，设：
定义\(\operatorname{opt}(i)\)表示计算\(f(i)\)时最优的那个决策点\(j\)，称其满足决策单调性当且仅当对于任意\(i < j\)满足\(\operatorname{opt}(i) \le \operatorname{opt}(j)\)。
性质\(1\)：
若\(w(i, j)\)满足四边形不等式，则\(f(i)\)满足决策单调性。
考虑反证法，若存在\(i < j\)且\(x = \operatorname{opt}(i) > y = \operatorname{opt}(j)\)，那么根据定义有\(w(x, j) \ge w(y, j), w(y, i) \ge w(x, i)\)，于是\(w(x, j) + w(y, i) \ge w(y, j) + w(x, i)\)，违反了四边形不等式，于是得证。
性质\(2\)：
如果对于任意\(i, j\)满足\(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)，那么\(w\)满足四边形不等式。
证明比较显然，考虑\(w(i + 1, j) + w(i, j + 1) - w(i, j) - w(i + 1, j + 1) \ge 0\)，这表示\(w\)的二维差分矩阵非负；于是考察其二维差分矩阵上一个子矩阵\((b + 1, d + 1), (a, c)\)的和必然也非负，即\(w(a, d) - w(a, c) - w(b, d) + w(b, c) \ge 0\)，这是四边形不等式的定义。
上面那个决策单调性太特殊了，只对\(f(i) = \min w(j, i)\)生效，感觉没有什么实际用途，一般都是这种问题：将序列分段使得权值最小，即：
这种怎么办？考虑：
性质\(3\)：
若\(w(i, j)\)满足四边形不等式，则\(w(i, j) = x_i + y_j\)也满足。
这是显然的，带入进去把\(x, y\)都消掉了。
于是只需要\(w(i, j)\)满足四边形不等式，则上面\(f(i)\)的转移也满足决策单调性。
如果强制钦定了要分\(k\)段，可以根据情况使用 wqs 二分或者多加一维解决。
考虑\(w(l, r)\)可能是\(\sum_{l \le i \le j \le r} c(i, j)\)的形式：
性质\(4\)：
若\(c(i, j) \ge 0\)，则\(w(l, r) = \sum_{l \le i \le j \le r} c(i, j)\)满足四边形不等式。
考虑证明\(w(x, y) + w(x + 1, y + 1) \le w(x, y + 1) + w(x + 1, y)\)，考虑拆贡献\(x + 1 \le i \le j \le y\)的\((i, j)\)对两边贡献是相同的，然后左边是\(\sum_{i = x, j \in [x, y]} c_{i, j} + \sum_{i \in [x + 1, y + 1], j = y + 1} c_{i, j}\)，然后右边\(w(x, y + 1)\)去掉\(x + 1 \le i \le j \le y\)的\((i, j)\)后是\(\sum_{i = x,j \in [x, y + 1]} c(i, j) + \sum_{i \in [x, y + 1], j = y + 1} c(i, j)\)，于是右边多考虑了\(c(x, y + 1)\)，得证。
例题
P1880 [NOI1995] 石子合并
考虑区间 dp，定义\(dp(l, r)\)表示将区间\([l, r]\)合并的最小代价，于是有转移：
钦定\(l\)固定时，有\(w(i, j) = dp(l, i) + dp(i + 1, j)\)，考虑证明\(w(i, j)\)满足四边形不等式，你推下式子发现等价于证明\(dp(i, j)\)满足四边形不等式。
这里\(dp(i, j)\)满足四边形不等式的充要条件是\(h(i, j) = s_i - s_{j - 1}\)也满足四边形不等式且满足区间包含单调性，可以对长度数学归纳发得到。
然后你发现上面固定右端点\(r\)时也有决策单调性，于是有\(\operatorname{opt}(l, r) \in [\operatorname{opt}(l, r - 1), \operatorname{opt}(l + 1, r)]\)，所以这样枚举决策点时间复杂度就是\(O(n^2)\)的。
link
于是可以得到性质\(5\)：
设\(w(l, r)\)满足四边形不等式且满足区间包含单调性，若\(dp(l, r) = w(l, r) + \min\limits_{k = l}^{r - 1} (dp(l, k) + dp(k + 1, r))\)，那么\(dp(l, r)\)也满足四边形不等式；且固定\(l\)或者固定\(r\)时都满足决策单调性，即\(\operatorname{opt}(l, r) \in [\operatorname{opt}(l, r - 1), \operatorname{opt}(l + 1, r)]\)。
类似题目 UVA10304 Optimal Binary Search Tree。
CF868F Yet Another Minimization Problem
考虑\(c(i, j) = [a_i = a_j]\)，那么\(w(l, r) = \sum_{l \le i \le j \le r} c(i, j)\)满足四边形不等式，于是\(dp\)时：
这个最优决策\(k\)具有单调性；考虑用分治与整体二分的思想解决。
即我们定义\(solve(l, r, kl, kr)\)表示目前在转移\([l, r]\)内的点，其最优决策点在\([kl, kr]\)内；那么可以暴力算出\(mid\)的最优决策点\(kmid\)，然后递归到\(solve(l, mid - 1, kl, kmid), solvew(mid + 1, r, kmid, kr)\)；显然递归层数使用\(\log n\)层，且每层\([kl, kr]\)的总长度是\(O(n)\)级别的，于是单次时间复杂度是\(O(n \log n)\)。
现在问题在于如何快速算\(w(l, r)\)，你考虑用类似莫队的走指针方式解决，你发现每次移动的长度是\(O(len)\)级别的，于是最终是\(O(n \log n)\)次。
总时间复杂度为\(O(nk \log n)\)。
link
P3515 [POI 2011] Lightning Conductor
这题你推一下式子，若对于\(i\)的答案是\(k\)，那么要对于所有\(j\)满足：
于是：
考虑怎么算\(h_j + \sqrt{|i - j|}\)，这里分讨\(j < i\)和\(j > i\)两种情况算就可以去掉绝对值，然后\(w(i, j) = \sqrt{i - j}\)，容易发现\(w\)满足四边形不等式，于是有决策单调性。
于是分治解决即可，时间复杂度为\(O(n \log n)\)。
link
P4767 [IOI 2000] 邮局 加强版
显然对于每个设立的邮局，到其距离最近的村庄集合是集合，于是可以设立状态\(dp_{i, j}\)表示考虑前\(i\)个村庄放了\(j\)个邮局的最小代价：
其中\(w(l, r)\)表示在区间\([l, r]\)内放一个邮局的最小代价，显然将邮局放在中位数位置最优，于是可以增量递推：
你发现\(w\)满足四边形不等式，于是我们按照\(j\)分层每层分治计算即可，时间复杂度为\(O(nk \log n)\).
link
这里证明一下上面的\(w\)满足四边形不等式，即\(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)；首先注意到\([i, j + 1]\)与\([i + 1, j]\)的中位数一样，设为\(k\)；
那么\(w(i, j + 1) = w(i + 1, j) + a_k - a_i + a_{j + 1} - a_k = w(i + 1, j) + a_{j + 1} - a_i\)，于是\(w(i, j + 1) + w(i + 1, j) = 2w(i + 1, j) + a_{j + 1} - a_i\)。
然后根据\(w\)的最小性的定义，可以得到\(w(i, j) \le w(i + 1, j) + a_k - a_i, w(i + 1, j + 1) \le w(i + 1, j) + a_{j + 1} - a_k\)，于是\(w(i, j) + w(i + 1, j + 1) \le 2w(i + 1, j) + a_{j + 1} - a_i = w(i, j + 1) + w(i + 1, j)\)得证。
P10861 [HBCPC2024] MACARON Likes Happy Endings
洛谷同步题解。
令\(s\)为前缀异或，那么\(c(i, j) = [s_j \oplus s_{i - 1} = d] \ge 0\)，于是\(w(l, r) = \sum_{l \le i \le j \le r}\)满足四边形不等式，于是\(dp\)时：
然后分治去做，计算\(w(k, i)\)可以简单走指针计算，于是时间复杂度是\(O(nk \log n)\)的。
link
