四边形不等式优化

一句话理解

四边形不等式：C(a,c)+C(b,d) ≤ C(a,d)+C(b,c)。

为什么要学

推出决策单调，区间 DP 变 n²。

讲解

要证明费用满足。

例子

石子合并有时能用。

常见错误

• 没验证就加速。
• 只背复杂度。