草。好难。Hootime 是不是不适合学 OI。
以下的 \(\mathrm{opt}(i)\) 表示位置为 \(i\) 的最优决策点。
从四边形不等式讲起
四边形不等式
若无特殊说明，以下均保证 \(a \le b \le c \le d\)。
是一个不等式（废话），长这样：
其中 \(a \le b \le c \le d\)。
这个东西还有另一种形式：
简记为「交叉小于包含」。
下证两个式子等价。
充分性很容易证明，只需要将代入 \(a' = a, b' = a+1, c' = b, d' = b+1\) 代入 \((1)\) 即可。
必要性：
我们将 \((2)\) 改写为如下形式：
\[w(a+1, c+1)-w(a+1, c) \le w(a, c+1)-w(a, c) \tag{1.1} \]那么我们使用数学归纳法，假设 \(w(b-1, c+1)-w(b-1, c) \le w(a, c+1)-w(a, c)\)
由 \((1.1)\) 得，\(w(b, c+1)-w(b, c) \le w(b-1, c+1)-w(b-1, c)\)
合并两式，得
\[w(b, c+1)-w(b, c) \le w(a, c+1)-w(a, c) \tag{1.2} \]又改写 \((1.2)\) 得：
\[w(b, c+1)-w(a, c+1) \le w(b, c)-w(a, c) \tag{1.3} \]我们再次使用数学归纳法，假设 \(w(b, d-1)-w(a, d-1) \le w(b, c)-w(a, c)\)
那么同理，可得：
\[w(b, d)-w(a, d) \le w(b, c)-w(a, c) \tag{1.4} \]移项得：
\[w(a, c)+w(b, d) \le w(a, d)+w(b, c) \]
经典结论
1
对于问题：\(f_i = \min_{1 \le j \le i} w(j, i)\)，如果 \(w\) 满足四边形不等式且 \(i < i'\)，有 \(\mathrm{opt}(i) \le \mathrm {opt}(i')\)。
下证性质的正确性。
反证法。设存在 \(i < i'\) 且 \(\mathrm{opt}(i) > \mathrm {opt}(i')\)。
设 \(j \leftarrow \mathrm{opt}(i), j' \leftarrow \mathrm {opt}(i')\)。整理如上不等关系得 \(j' < j \le i < i'\)。
又由最优性可得，\(w(j, i) < w(j', i), w(j', i') < w(j, i')\)。
将两式相加得 \(w(j, i)+w(j', i') < w(j', i)+w(j, i')\)，即 \(w(j', i)+w(j, i') > w(j, i)+w(j', i')\)。
我们用 \(a, b, c, d\) 代替 \(j', j, i, i'\)，发现式子变成了 \(w(a, c)+w(b, d) > w(a, d)+w(b, c)\)，与四边形不等式矛盾。