四边形不等式优化是对特定形式的状态转移方程进行优化的一种方法。
开坑！
对于 2D1D 的 DP（比如石子合并一类的区间 DP）： \[ f_{i,j}=\min_{i\le k<j}\{f_{i,k}+f_{k+1,j}\}+cost(i,j) \] 可以通过四边形不等式从 \(\mathcal O(n^3)\) 优化到 \(\mathcal O(n^2)\)。
step 1：证明 cost 为凸
对于 \(i<i+1\le j<j+1\)： \[ w(i,j)+w(i+1,j+1)\le w(i+1,j)+w(i,j+1) \]
step 2：证明 DP 为凸
同理，对于 \(i<i+1\le j<j+1\)： \[ f(i,j)+f(i+1,j+1)\le f(i+1,j)+f(i,j+1) \]
step 3：证明决策单调性
设 \(g(i,j)\) 为 \(f(i,j)\) 的最优决策点： \[ g(i,j-1)\le g(i,j) \le g(i+1,j) \]
应用
猜单调性后打表证明。
发现不行就改改式子往上套。
咕~