四边形不等式学习笔记

liheyang123 · 2026-02-07 10:59:32 · 算法·理论

定义

四边形不等式是针对一个二元函数 \operatorname{w}(x,y) 所定义，若有 \forall x_1\leq x_2\leq y_1\leq y_2,\operatorname{w}(x_1,y_1)+\operatorname{w}(x_2,y_2)\leq\operatorname{w}(x_1,y_2)+\operatorname{w}(x_2,y_1)，则认为二元函数 \operatorname{w}(x,y) 满足四边形不等式。

同时有一个等价结论 \forall x\leq y,\operatorname{w}(x,y)+\operatorname{w}(x+1,y+1)\leq\operatorname{w}(x,y+1)+\operatorname{w}(x+1,y)。

同时也可以注意到，如果 \operatorname{f}(x,y),\operatorname{g}(x,y) 均满足四边形不等式，则 \operatorname{h}(x,y)=\operatorname{f}(x,y)+\operatorname{g}(x,y) 同样满足四边形不等式。

同时定义决策单调性，\forall i<j,\operatorname{o}(i)\leq\operatorname{o}(j)，其中 \operatorname{o}(i) 指位置 i 的最优决策点。

优化

假设已知 \operatorname{w}(x,y) 满足四边形不等式，现在要求出 \operatorname{f}(i)=\min\limits_{j<=i} \operatorname{w}(j,i)。

现在证明由 \operatorname{w}(x,y) 推知决策单调性，设上述问题中最优决策点为 p_i，假设 \exist i<j,p_i>p_j，显然 p_j<p_i<i<j 那么有 \operatorname{w}(p_j,i)+\operatorname{w}(p_i,j)\leq\operatorname{w}(p_i,i)+\operatorname{w}(p_j,j)。

又有 \operatorname{w}(p_i,i)\leq\operatorname{w}(p_j,i),\operatorname{w}(p_j,j)\leq\operatorname{w}(p_i,j) 故矛盾。

实现

考虑到不需要掌握所有有关的实现，这里只介绍最为实用的。

分治处理转移较为复杂的原因是 p_{mid} 的计算依赖于 [pl,mid) 的答案，放弃求出 p_{mid} 的正确性，只保证 [0,pl] 上的正确性，即不立即保证 p_{mid} 的全局最优性，而是通过递归逐步收敛。

记只考虑 [0,pl] 时 x 的最优决策点为 p_{x,pl}，注意到如果要继续递归，需要 p_{mid,pl},p_{x,mid}，对于 p_{mid,pl} 可以递归后枚举 [p_{pl},p_{x,pl} 内的所有决策点，对于 p_{x,mid} 可以在 (pl,mid] 计算完之后暴力枚举这个区间算出，神秘地发现，这算出了正确的 f_i 与 p_i。

考虑分治处理假设当前处理的区间是 (pl,pr]，而 [0,pl] 均已完成了正确的计算，而 pr 都已经算出了在 [0,pl] 中的疑似最优决策点，这个疑似最优决策点指的是仅考虑 [0,pl] 时的最优决策点。

有下述几个步骤

1. 现在已知只考虑 [0,pl] 的时的 pr 的最优决策点，把 pl 的决策点到 pr 的疑似最优决策点之间的所有点转移到 mid，计算并更新 f_{mid} 与 mid 的疑似最优决策点。 这里展开解释一下，显然满足了可以递归处理的前提，由于决策单调性，所以只考虑 f_{pl} 与 f_{pr} 的疑似最优决策点是正确的。
2. 递归处理 (pl,mid]。
3. 再将 [pl+1,mid] 的最优决策点转移到 pr，计算并更新 f_{pr} 与 pr 的疑似最优决策点。
4. 递归处理 (mid,pr]。

该分治策略的正确性依赖于决策单调性所保证的决策区间包含关系，具体可以查看原文。

小结一下，在什么条件下使用四边形不等式优化。

何时使用四边形不等式优化？

• DP 形如 f(i) = \min_{j < i} \{ f(j) + w(j+1, i) \}。
• 代价函数 w 满足四边形不等式。

前面介绍的部分主要是求最小值，求最大值也是同理，可以结合例题思考。

例题

「POI2011 R1」避雷针 Lightning Conductor

问题等价于求 \forall j,k_i\geq h_j-h_i+\sqrt{|i-j|}。 先拆绝对值，假设 j\leq i，可以写成以下形式 f_i=k_i，w_{i,j}=h_j-h_i+\sqrt{i-j}。