\(1.\)四边形不等式定义
就是满足 \(f(l_1, r_1)+f(l_2,r_2) \le f(l_1,r_2)+f(l_2,r_1), l_1 \le l_2 \le r_1 \le r_2\)。
说人话就是相交 \(\le\) 包含
至于为什么叫四边形不等式优化，它可以类比四边形对边长度和 \(\le\) 对角线长度和。
\(2.\)优化
如果要能优化，先得满足两个条件第一个就是上面的四边形不等式，第二个是 \(f(l_1,r_1) \le f(l_2,r_2),l_2\le l_1\le r_1 \le r_2\)。
比如说对于一个区间DP \(dp_{i,j} = \min\limits_{i\le k < j} (dp_{i,k} + dp_{k + 1,j} + w_{i,j})\)。
有两个结论。
\(1.\) 若 \(w_{i,j}\) 满足结论，那么 \(dp_{i,j}\) 也满足。
\(2.\) 设 \(dp_{i,j}\) 的最优决策点是 \(a_{i,j}\)，就有\(a_{i,j - 1} \le a_{i, j} \le a_{i + 1, j}\)。
证明可以看oi-wiki。
标签：le,不等式,满足,四边形,优化,dp From： https://www.cnblogs.com/Hovery/p/16951526.html