本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-23 14:17:51

四边形不等式

$$a \le b \le c \le d, w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$

即，交叉小于包含。

如果有方程

$$f(i) = \min\limits_{1\le j \lt i} w(j, i)$$

设在 $i$ 点的决策点为 $q(i)$，要证 $j \lt i, q(j) \le q(i)$

设有 $c \lt d$，但 $q(c) = b \gt q(d) = a$，那么首先有

$$a \lt b \le c \lt d$$

于是由最优

$$w(a, c) \gt w(b, c), w(b, d) \gt w(a, d)$$

两式相加得

$$w(a, c) + w(b, d) \gt w(a, d) + w(b, c)$$

但是这与四边形不等式矛盾。

简单证明 P3195 玩具装箱有决策单调性

$$w(i, j) = (s_i - s_j - L)^2 = O((s_i - s_j)^2)$$

其中 $s_i$ 是单调增的，那么对 $i \lt j$，有

$$w(i, j - 1) + w(i + 1, j) \lt w(i, j) + w(i + 1, j - 1)$$

也即

$$(s_i-s_{j-1})^2 + (s_{i+1}-s_j)^2 \lt (s_i - s_j)^2 + (s_{i+1}-s_{j-1})^2$$

$$(s_i-s_{j-1}+s_i - s_j)(s_i-s_{j-1}-s_i+s_j) \lt (s_{i+1}-s_{j-1}+s_{i+1}-s_j)(s_{i+1}-s_{j-1}-s_{i+1}+s_j)$$

$$(2s_i - s_j - s_{j-1})(s_j - s_{j-1}) \lt (2s_{i+1}-s_j - s_{j-1})(s_j - s_{j-1})$$

由于 $s_j - s_{j-1} \gt 0$，那么

$$2s_i - s_j - s_{j-1}\lt s_{i+1}-s_j - s_{j-1}$$

也就是 $s_i \lt s_{i+1}$，由单调性得证。