四边形不等式

定义

对于二元函数 \(f(x, y)\)，若 \(\forall a \leq b \leq c \leq d\)，有 \(f(a, d) + f(b, c) \geq f(a, c) + f(b, d)\)，则称函数 \(f\) 满足四边形不等式。

判定定理

对于二元函数 \(f(x, y)\)，若 \(\forall a < b\) 有 \(f(a, b + 1) + f(a + 1, b) \geq f(a, b) + f(a + 1, b + 1)\) 则函数 \(f\) 满足四边形不等式。

证明

使用数学归纳法，假设 \(b = a + k + 1, 0 \leq k < c - a - 1\) 时，有：

\[ f(a, c + 1) + f(b, c) \geq f(a, c) + f(b, c + 1) \tag{1} \\ \]

因为 \(b < c\)，所以：

\[ f(b, c + 1) + f(b + 1, c) \geq f(b, c) + f(b + 1, c + 1) \tag{2} \\ \]

\((1) + (2)\) 得：

\[ f(a, c + 1) + f(b + 1, c) \geq f(a, c) + f(b + 1, c + 1) \\ \]

所以上式对 \(b = a + k + 2\) 同样成立。

因为当 \(a = b\) 时，上式显然成立，所以 \(\forall a \leq b \leq c\)，有 \(f(a, c + 1) + f(b, c) \geq f(a, c) + f(b, c + 1)\)。

假设 \(d = c + k + 1, k \geq 0\) 时，有：

\[ f(a, d) + f(b, c) \geq f(a, c) + f(b, d) \tag{3} \\ \]

因为 \(a \leq b \leq d\)，所以：

\[ f(a, d + 1) + f(b, d) \geq f(a, d) + f(b, d + 1) \tag{4} \\ \]

\((3) + (4)\) 得：

\[ f(a, d + 1) + f(b, c) \geq f(a, c) + f(b, d + 1) \\ \]

所以上式对 \(d = c + k + 2\) 同样成立。

因为当 \(c = d\) 时，上式显然成立，所以 \(\forall a \leq b \leq c \leq d\)，有 \(f(a, d) + f(b, c) \geq f(a, c) + f(b, d)\)，因此 \(f\) 满足四边形不等式。

优化一维线性 DP

一维决策单调性

结论

若有转移方程 \(\displaystyle dp_i = \min_{1 \leq j < i} \{dp_j + f(j, i) \}\)，\(p_i\) 为 \(dp_i\) 取到最小值的 \(j\)，且 \(f\) 满足四边形不等式，则 \(p_i\) 单调不降。

证明

对于 \(1 \leq k < p_i\)，因为 \(p_i\) 的最优性，有：

\[ dp_{p_i} + f(p_i, i) \leq dp_k + f(k, i) \tag{5} \\ \]

因为 \(f\) 满足四边形不等式，所以对于 \(i + 1 \leq i' \leq n\)，有：

\[ f(p_i, i') + f(k, i) \leq f(p_i, i) + f(k, i') \tag{6} \\ \]

\((5) + (6)\) 得：

\[ dp_{p_i} + f(p_i, i') \leq dp_k + f(k, i') \\ \]

也就是说，对于 \(dp_{i'}\) 而言，\(p_i\) 比 \(k < p_i\) 更优。

优化二维区间 DP

结论

若有转移方程 \(\displaystyle dp_{i, j} = \min_{i \leq k < j} \{dp_{i, k} + dp_{k + 1, j} + f(i, j) \}\)，且 \(f\) 满足四边形不等式，且对于 \(\forall a \leq b \leq c \leq d \leq\)，有 \(f(a, d) \geq f(b, c)\)，则 \(dp\) 满足四边形不等式。

证明

对于 \(j = i + 1\)，\(dp_{i, j} = dp_{i, i} + dp_{i + 1, i + 1} + f(i, i + 1) = f(i, i + 1)\)。

若 \(dp_{i, j + 1}\) 的决策点是 \(i\)，则 \(dp_{i, j + 1} = dp_{i, i} + dp_{i + 1, j + 1} + f(i, i + 2) = dp_{i + 1, j + 1} + f(i, i + 2)\)。因为 \(f(i, i + 2) \geq f(i, i + 1) = dp_{i, j}\)，所以 \(dp_{i, j + 1} = dp_{i + 1, j + 1} + f(i, i + 2) \geq dp_{i + 1, j + 1} + dp_{i, j}\)。

若 \(dp_{i, j + 1}\) 的决策点是 \(i + 1\)，则 \(dp_{i, j + 1} = dp_{i, i + 1} + dp_{i + 2, j + 1} + f(i, i + 2) = dp_{i, j} + f(i, i + 2)\)。因为 \(f(i, i + 2) \geq f(i + 1, i + 2) = dp_{i + 1, j + 1}\)，所以 \(dp_{i, j + 1} = dp_{i, j} + f(i, i + 2) \geq dp_{i, j} + dp_{i + 1, j + 1}\)。

因为 \(dp_{i + 1, j} = 0\)，所以对于 \(i + 1 = j\)，有 \(dp_{i, j + 1} + dp_{i + 1, j} \geq dp_{i, j} + dp_{i + 1, j + 1}\)，\(dp\) 满足四边形不等式。

使用数学归纳法，假设 \(i + k < j, k \geq 0\) 时有 \(dp\) 满足四边形不等式，\(dp_{i + 1, j}\) 的决策点是 \(x\)，\(dp_{i, j + 1}\) 的决策点是 \(y\)，且 \(i + 1 \leq x \leq j - 1, i \leq y \leq j\)，因为 \(x, y\) 的最优性，有：

\[ dp_{i + 1, j} + dp_{i, j + 1} = dp_{i + 1, x} + dp_{x + 1, j} + f(i + 1, j) + dp_{i, y} + dp_{y + 1, j + 1} + f(i, j + 1) \\ \tag{7} \]

若 \(i + 1 \leq x \leq y \leq j\) 且 \(x < j\)，\(x, y\) 对于 \(dp_{i, j}, dp_{i + 1, j + 1}\) 不一定最优，所以：

\[ dp_{i, j} + dp_{i + 1, j + 1} \leq dp_{i, x} + dp_{x + 1, j} + f(i, j) + dp_{i + 1, y} + dp_{y + 1, j + 1} + f(i + 1, j + 1) \tag{8} \\ \]

若 \(i \leq y \leq x \leq j - 1\) 且 \(x > i\)，\(x, y\) 对于 \(dp_{i + 1, j + 1}, dp_{i, j}\) 不一定最优，所以：

\[ dp_{i + 1, j + 1} + dp_{i, j} \leq dp_{i + 1, x} + dp_{x + 1, j + 1} + f(i + 1, j + 1) + dp_{i, y} + dp_{y + 1, j} + f(i, j) \tag{9} \\ \]

因为 \(f\) 满足四边形不等式，所以：

\[ f(i, j) + f(i + 1, j + 1) \leq f(i + 1, j) + f(i, j + 1) \tag{10} \\ \]

因为归纳假设，所以：

\[ dp_{i, x} + dp_{i + 1, y} \leq dp_{i + 1, x} + dp_{i, j} \tag{11} \\ \]

\[ dp_{x + 1, j + 1} + dp_{y + 1, j} \leq dp_{x + 1, j} + dp_{y + 1, j + 1} \tag{12} \\ \]

\((7) + (8) + (10) + (11)\) 或 \((7) + (9) + (10) + (12)\) 得：

\[ dp_{i, j} + dp_{i + 1, j + 1} \leq dp_{i + 1, j} + dp_{i, j + 1} \\ \]

即 \(i + k = j\) 时 \(dp\) 也满足四边形不等式。

二位决策单调性

若有转移方程 \(\displaystyle dp_{i, j} = \min_{i \leq k < j} \{dp_{i, k} + dp_{k + 1, j} + f(i, j) \}\)，且 \(dp\) 满足四边形不等式，记 \(p_{i, j}\) 为 \(dp_{i, j}\) 的决策点，则 \(p_{i, j - 1} \leq p_{i, j} \leq p_{i + 1, j}\)。

证明

若 \(i < k < p_{i, j}\)，因为 \(p_{i, j}\) 的最优性，有：

\[ dp_{i, (p_{i, j})} + dp_{(p_{i, j})+ 1, j} + f(i, j) \leq dp_{i, k} + dp_{k + 1, j} + f(i, j) \\ dp_{i, (p_{i, j})} + dp_{(p_{i, j})+ 1, j} \leq dp_{i, k} + dp_{k + 1, j} \tag{13} \\ \]

因为 \(dp\) 满足四边形不等式，所以：

\[ dp_{i, k} + dp_{i + 1, (p_{i, j})} \leq dp_{i, (p_{i, j})} + dp_{i + 1, k} \tag{14} \\ \]

\((13) + (14)\) 得：

\[ dp_{i + 1, (p_{i, j})} + dp_{(p_{i, j})+ 1, j} \leq dp_{i + 1, k} + dp_{k + 1, j} \\ \]

因此，对于 \(dp_{i + 1, j}\) 而言，\(p_{i, j}\) 比 \(i < k < p_{i, j}\) 更优，也就是说 \(p_{i + 1, j} \geq p_{i, j}\)。

若 \(p_{i, j} < k < j - 1\)，因为 \(p_{i, j}\) 的最优性，有：

\[ dp_{i, (p_{i, j})} + dp_{(p_{i, j})+ 1, j} + f(i, j) \leq dp_{i, k} + dp_{k + 1, j} + f(i, j) \\ dp_{i, (p_{i, j})} + dp_{(p_{i, j})+ 1, j} \leq dp_{i, k} + dp_{k + 1, j} \tag{15} \\ \]

因为 \(dp\) 满足四边形不等式，所以：

\[ dp_{k + 1, j} + dp_{(p_{i, j}) + 1, j - 1} \leq dp_{(p_{i, j}) + 1, j} + dp_{k + 1, j - 1} \tag{16} \\ \]

\((15) + (16)\) 得：

\[ dp_{i, (p_{i, j})} + dp_{(p_{i, j}) + 1, j - 1} \leq dp_{i, k} + dp_{k + 1, j - 1} \\ \]

因此，对于 \(dp_{i, j - 1}\) 而言，\(p_{i, j}\) 比 \(p_{i, j} < k < j - 1\) 更优，也就是说 \(p_{i, j - 1} \leq p_{i, j}\)。