四边形不等式如何应用于复杂几何问题？

四边形不等式 我们称一个二元函数 \(w(i, j)\) 满足四边形不等式，当且仅当对于任意 \(a \le b \le c \le d\) 满足： \[w(a, c) + w(b, d) \le w(a, d) + w(b, c) \] 即交叉小于包含。 其可以用来对转移进行优化，具体的，设： \[f(i) = \min_{j \le i} w(j, i) \] 定义 \(\operatorname{opt}(i)\) 表示计算 \(f(i)\) 时最优的那个决策点 \(j\)，称其满足决策单调性当且仅当对于任意 \(i < j\) 满足 \(\operatorname{opt}(i) \le \operatorname{opt}(j)\)。 性质 \(1\)： 若 \(w(i, j)\) 满足四边形不等式，则 \(f(i)\) 满足决策单调性。 考虑反证法，若存在 \(i < j\) 且 \(x = \operatorname{opt}(i) > y = \operatorname{opt}(j)\)，那么根据定义有 \(w(x, j) \ge w(y, j), w(y, i) \ge w(x, i)\)，于是 \(w(x, j) + w(y, i) \ge w(y, j) + w(x, i)\)，违反了四边形不等式，于是得证。 性质 \(2\)： 如果对于任意 \(i, j\) 满足 \(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)，那么 \(w\) 满足四边形不等式。 证明比较显然，考虑 \(w(i + 1, j) + w(i, j + 1) - w(i, j) - w(i + 1, j + 1) \ge 0\)，这表示 \(w\) 的二维差分矩阵非负；于是考察其二维差分矩阵上一个子矩阵 \((b + 1, d + 1), (a, c)\) 的和必然也非负，即 \(w(a, d) - w(a, c) - w(b, d) + w(b, c) \ge 0\)，这是四边形不等式的定义。 上面那个决策单调性太特殊了，只对 \(f(i) = \min w(j, i)\) 生效，感觉没有什么实际用途，一般都是这种问题：将序列分段使得权值最小，即： \[f(i) = \min_{j \le i} f(j - 1) + w(j, i) \] 这种怎么办？考虑： 性质 \(3\)： 若 \(w(i, j)\) 满足四边形不等式，则 \(w(i, j) = x_i + y_j\) 也满足。 这是显然的，带入进去把 \(x, y\) 都消掉了。 于是只需要 \(w(i, j)\) 满足四边形不等式，则上面 \(f(i)\) 的转移也满足决策单调性。 如果强制钦定了要分 \(k\) 段，可以根据情况使用 wqs 二分或者多加一维解决。 考虑 \(w(l, r)\) 可能是 \(\sum_{l \le i \le j \le r} c(i, j)\) 的形式： 性质 \(4\)： 若 \(c(i, j) \ge 0\)，则 \(w(l, r) = \sum_{l \le i \le j \le r} c(i, j)\) 满足四边形不等式。 考虑证明 \(w(x, y) + w(x + 1, y + 1) \le w(x, y + 1) + w(x + 1, y)\)，考虑拆贡献 \(x + 1 \le i \le j \le y\) 的 \((i, j)\) 对两边贡献是相同的，然后左边是 \(\sum_{i = x, j \in [x, y]} c_{i, j} + \sum_{i \in [x + 1, y + 1], j = y + 1} c_{i, j}\)，然后右边 \(w(x, y + 1)\) 去掉 \(x + 1 \le i \le j \le y\) 的 \((i, j)\) 后是 \(\sum_{i = x,j \in [x, y + 1]} c(i, j) + \sum_{i \in [x, y + 1], j = y + 1} c(i, j)\)，于是右边多考虑了 \(c(x, y + 1)\)，得证。