考虑 \(a\leq b\leq c\leq d\)
最小化问题中，四边形不等式为 \(w(a,c)+w(b,d)\leq w(a,d)+w(b,c)\)。
最大化问题中，四边形不等式为 \(w(a,c)+w(b,d)\geq w(a,d)+w(b,c)\)。
交叉优于包含。
文中默认讨论最小化问题。
随感 - 感受凸性、决策单调性、次模性、四边性不等式之间千丝万缕的联系
Itst APIO2021四边形不等式讲稿（内容：决策单调性优化，二维决策单调性，决策单调性最短路，蒙日矩阵）
决策单调性
考虑 DP \(f_i=\min\limits_{j<i}\{w(j,i)\}\) 或 \(f_i=\min\limits_{j<i}\{c_j+w(j,i)\}\)（第二种形式对应区间划分 DP），其中 \(w(j,i)\) 满足四边形不等式，不难发现 \(\min\) 中的式子均满足四边形不等式（带入证明即可），不妨只证明第一种形式的决策单调性。
设 \(opt(i)<i\) 满足 \(\forall j<i,w(j,i)\geq w(opt(i),i)\) 且 \(\forall j<opt(i),w(j,i)>w(opt(i),i)\)。
反证法，若 \(c<d\) 且 \(opt(c)>opt(d)\)，则
则
即
与四边形不等式矛盾。
四边形不等式->凸性
在区间划分问题中，如果权值数组满足四边形不等式，则答案对区间数量有凸性，参考（翻译）浅谈满足四边形不等式的序列划分问题的答案凸性 - Itst，以后再搬。
最小化问题有下凸性，反之亦然。
蒙日矩阵
- 性质1：设矩阵 \(A\) 是蒙日矩阵，则 \((A^k)_{i,j}\) 关于 \(k\) 有凸性（四边形不等式->凸性）
蒙日矩阵乘法
考虑两个相同大小的蒙日方阵 \(A,B\)，定义 \(C=A\times B\) 满足：
显然有 \(\mathcal O(n^3)\) 做法，考虑优化：
设 \(K_{i,j}\) 满足 \(\forall k,A_{i,k}+B_{k,j}\geq A_{i,K_{i,j}}+B_{K_{i,j},j}\)，即 \(C_{i,j}\) 决策点。
首先证明 \(C\) 也是蒙日矩阵：
当 \(a\leq b\leq c\leq d\) 时，设 \(K_{a,d}=x,K_{b,c}=y\)，不妨设 \(x\leq y\)。
\(x>y\) 的情况交换第一行 \(x,y\)，后面类似推导即可。
接下来证明二维决策单调性，即 \(K_{i,j-1}\leq K_{i,j}\leq K_{i+1,j}\)：
对于 \(K_{i,j-1}\leq K_{i,j}\)，考虑看成左端点为 \(i\) 的一维DP，决策单调性自然成立。
对于 \(K_{i,j}\leq K_{i+1,j}\)，看成倒着的一维DP，注意到转移也满足四边形不等式，决策单调性也成立。
区间合并问题（最优搜索树问题）
即 \(f_{i,j}=\min\limits_{k}\{f_{i,k}+f_{k,j}\}+w(i,j)\)，其中 \(w\) 满足四边形不等式和区间单调性（若 \(i\leq i'\leq j'\leq j\)，\(w(i,j)\geq w(i',j')\)）。
与蒙日矩阵乘法类似，先证明 \(f\) 满足四边形不等式，再证明二维决策单调性，即可 \(\mathcal O(n^2)\) 做。
证明四边形不等式稍微有一些不同，在 \(a\leq b<c\leq d\) 时一样，在 \(a\leq b=c\leq d\) 时需要用 \(w\) 区间单调性证明：
对 \(d-a\) 归纳，\(d-a-1\) 成立时，考虑 \(d-a\) 是否成立。设 \(f_{a,d}\) 决策点为 \(x\)，若 \(x<b\)，则
\(x\geq b\) 时同理。
次模性
定义 \(f\) 为 \(U=\{0,1\}^m\) 上的实函数，则对于 \(S,T\subset U\)，满足：
常见满足四边形不等式的转移
- 区间颜色种数
- 把区间 \([l,r]\) 看成集合 \(S(l,r)\) ，区间拼接看成集合求并，则 \(w(l,r)=f(S(l,r))\) 满足次模性。
- 递增序列中一个区间里数的中位数到集合中所有数差的绝对值之和，把区间看成集合则也满足次模性
题单
P10181 龙逐千灯幻
P8864 「KDOI-03」序列变换
P6246 [IOI 2000] 邮局 加强版 加强版