四边形不等式问题详解

四边形不等式

设 $w(x, y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a, b, c, d$，其中 $a \leq b \leq c \leq d$，都有 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$ 成立，则称函数 $w$ 满足 四边形不等式

定理（四边形不等式的另一种定义）

设 $w(x, y)$ 是定义在整数集合上的二元函数，若对于定义域上的任意整数 $a, b$，其中 $a < b$，都有 $w(a, b + 1) + w(a + 1, b) \geq w(a, b) + w(a + 1, b + 1)$ 成立，则函数 $w$ 满足 四边形不等式

证明：

对于 $a < c$，有 $w(a, c + 1) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 1)$

对于 $a + 1 < c$，有 $w(a + 1, c + 1) + w(a + 2, c) \geq w(a + 1, c) + w(a + 2, c + 1)$

两式相加，对于 $a < a + 1 < c$，有 $w(a, c + 1) + w(a + 2, c) \geq w(a, c) + w(a + 2, c + 1)$

设 $a < b < c$，则可以用 $b$ 替换 $a + 1$，有 $w(a, c + 1) + w(b, c) \geq w(a, c) + w(b, c + 1)$

当 $a = b = c$ 时，有 $w(a, c + 1) + w(b, c) = w(a, c) + w(b, c + 1)$

因此，对于任意的 $a \leq b \leq c$，有 $w(a, c + 1) + w(b, c) \geq w(a, c) + w(b, c + 1)$

对于 $a < b < c$，有 $w(a, c + 1) + w(b, c) \geq w(a, c) + w(b, c + 1)$

对于 $a < b < c + 1$，有 $w(a, c + 2) + w(b, c + 1) \geq w(a, c + 1) + w(b, c + 2)$

再次两式相加，对于 $a < b < c < c + 1$，有 $w(a, c + 2) + w(b, c) \geq w(a, c) + w(b, c + 2)$

设 $d > c$，则可以用 $d$ 替换 $c + 1$，有 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$

当 $a = b = c = d$ 时，有 $w(a, d) + w(b, c) = w(a, c) + w(b, d)$

因此，对任意的 $a \leq b \leq c \leq d$，有 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$

证毕。

一维线性 dp 的四边形不等式优化

对于形如 $f[i] = min_{0 \leq j < i} \lbrace f[j] + val(j, i) \rbrace$ 的状态转移方程，记 $p[i]$ 为令 $f[i]$ 取到最小值的 $j$ 的值，即 $p[i]$ 是 $f[i]$ 的最优决策，若 $p$ 在 $[1, N]$ 上单调不减（非严格单调递增），则称 $f$ 具有决策单调性。

定理（决策单调性）

在状态转移方程 $f[i] = min_{0 \leq j < i} \lbrace f[j] + val(j, i) \rbrace$ 中，若函数 $val$ 满足四边形不等式，则 $f$ 具有决策单调性（对于 $a < b$，则有 $p[a] < p[b]$）。

证明：

$\forall i \in [1, N], \forall j \in [0, p[i] -1]$，根据 $p[i]$ 的最优性，有：$f[p[i]] + val(p[i], i) \leq f[j] + val(j, i)$

$\forall i’ \in [i + 1, N]$，已知 $j \leq p[i] \leq i \leq i’$，且 $val$ 满足四边形不等式，有：$val(j, i’) + val(p[i], i) \geq val(j, i) + val(p[i], i’)$

上式移项得：$val(p[i], i’) - val(p[i], i) \leq val(j, i’) - val(j, i)$

上式与第一个不等式相加，有：$f[p[i]] + val(p[i], i’) \leq f[j] + val(j, i’)$

这个不等式得含义为，以 $p[i]$ 作为 $f[i’]$ 的决策，比以 $j < p[i]$ 作为 $f[i’]$ 的决策更优。即 $f[i’]$ 的最优决策不可能小于 $p[i]$，即 $p[i’] \geq p[i]$，所以 $f$ 有决策单调性。

证毕。

当 f 有决策单调性时，我们可以把 $f[i] = min_{0 \leq j < i} \lbrace f[j] + val(j, i) \rbrace$ 的计算时间从 $O(N^2)$ 优化到 $O(NlogN)$

考虑对 $p$ 数组进行维护，最初 $p$ 数组全部为 $0$，到 $i$ 循环进行的任意时刻，根据 $p[i]$ 的单调性，$p$ 的情况如下图所示：

当求出一个新的 $f[i]$ 时，我们应该考虑 $i$ 可以作为哪些 $f[i’] (i’ > i)$ 的最优决策。根据决策单调性，最终我们会找到一个位置，在该位置之前，$p$ 数组目前存储的决策都比 $i$ 好，在该位置之后，$p$ 数组目前存储的决策都比 $i$ 差，我们要做的就是快速找到上述位置，在 $p$ 数组中把该位置之后的部分都变为 $i$。

直接修改一个数组效率当然很低，因此我们可以建立一个队列，代替 $p$ 数组。队列中保存若干个三元组 $(j, l, r)$，$j$ 表示决策，$l, r$ 表示目前 $p[l \sim r]$ 的值都是 $j$。

例如，第一幅图就可以用 $5$ 个三元组 $(j_1, 1, 2), (j_2, 3, 3), (j_3, 4, 6), (j_4, 7, 8), (j_5, 9, 12)$ 来表示。我们从队尾开始检查，判断出整个 $(j_4, 7, 8), (j_5, 9, 12)$ 都不如 $i$ 优，直接从队尾删除，而 $(j_3, 4, 6)$ 左端比 $i$ 优，右端比 $i$ 差，因此我们在 $(j_3, 4, 6)$ 里二分查找，即可确定所求的位置。最后我们把 $(j_3, 4, 6)$ 变为 $(j_3, 4, 5)$，把 $(i, 6, 12)$ 入队，即可得到第二幅图所示的情景。

另外，队列中没有必要保存小于 $p[1 \sim i-1]$ 的部分，我们可以通过检查队头来排除掉过时的决策，这样就可以像许多单调队列问题一样，直接取队头为最优决策。

总而言之，对于每个 $i \in [1, N]$，我们执行以下操作：

1. 检查队头：设队头为 $(j_0, l_0, r_0)$，若 $r_0 = i - 1$，删除队头，否则令 $l_0 = i$
2. 取队头保存的 $j$ 为最优决策，执行状态转移，计算出 $f[i]$
3. 尝试插入新决策 $i$，步骤如下：
   (1) 取出队尾，记为 $(j_t, l_t, r_t)$
   (2) 若对于 $f[l_t]$ 来说，$i$ 是比 $j_t$ 更优的决策，即 $f[i] + val(i, l_t) \leq f[j_t] + val(j_t, l_t)$，记为 $pos = l_t$，删除队尾，回到步骤 (1)
   (3) 若对于 $f[r_t]$ 来说，$j_t$ 是比 $i$ 更优的决策，即 $f[j_t] + val(j_t, r_t) \leq f[i] + val(i, r_t)$，去往步骤 (5)
   (4) 否则，对于 $[l_t, r_t]$ 上二分查找，求出位置 $pos$，在此之前决策 $j_t$ 更优，在此之后决策 $i$ 更优，去往步骤 (5)
   (5) 把三元组 $(i, pos, N)$ 插入队尾

例题：诗人小G

二维区间 dp 的四边形不等式优化

在区间 dp 问题，例如 “石子合并” 中，我们经常遇到下面这样的状态转移方程：

$$f[i][j] = min_{i \leq k < j} \lbrace f[i][k] + f[k + 1][j] + w(i, j) \rbrace$$

利用四边形不等式，也可以对该方程的状态转移进行优化。

定理

在状态转移方程 $f[i][j] = min_{i \leq k < j} \lbrace f[i][k] + f[k + 1][j] + w(i, j) \rbrace$ 中（规定 $f[i][i] = w(i, i) = 0$），如果下面两个条件成立：
1. $w$ 满足四边形不等式
2. 对于任意的 $a \leq b \leq c \leq d$，有 $w(a, d) \geq w(b, c)$

那么 $f$ 也满足四边形不等式。

证明

当 $i + 1 = j$ 时，$f[i][j + 1] + f[i + 1][j] = f[i][i + 2] + f[i + 1][i + 1] = f[i][i + 2]$

若 $f[i][i + 2]$ 的最优决策是 $i + 1$，则：
$$f[i][i + 2] = f[i][i + 1] + f[i + 2][i + 2] + w(i, i + 2) = w(i, i + 1) + w(i, i + 2)$$

$$\geq w(i, i + 1) + w(i + 1, i + 2) = f[i][i + 1] + f[i + 1][i + 2] = f[i][j] + f[i + 1][j + 1]$$

若 $f[i][i + 2]$ 的最优决策是 $i$，则：
$$f[i][i + 2] = f[i][i] + f[i + 1][i + 2] + w(i, i + 2) = w(i + 1, i + 2) + w(i, i + 2)$$

$$\geq w(i + 1, i + 2) + w(i, i + 1) = f[i + 1][i + 2] + f[i][i + 1] = f[i + 1][j + 1] + f[i][j]$$

故当 $j - i = 1$ 时，$f[i][j + 1] + f[i + 1][j] \geq f[i][j] + f[i + 1][j + 1]$，即四边形不等式对 $f[i][j]$ 成立。

接下来，用数学归纳法，假设当 $j - i < k$ 时，四边形不等式对 $f[i][j]$ 成立，考虑 $j - i = k$ 的情况，设 $f[i][j + 1]$ 以 $x$ 为最优决策，$f[i + 1][j]$ 以 $y$ 为最优决策。不妨设 $i + 1 \leq x \leq y$。

根据 $x$ 和 $y$ 的最优性，有:

$f[i][j + 1] + f[i + 1][j]$

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

对于 $f[i][j]$ 和 $f[i + 1][j + 1]$，$x$ 和 $y$ 是任意决策（不一定最优），故：

$f[i][j] + f[i + 1][j + 1] \leq$

$$f[i][x] + f[x + 1][j] + w(i, j) + f[i + 1][y] + f[y + 1][j + 1] + w(i + 1, j + 1) \tag{2}$$

因为 $w$ 满足四边形不等式，所以：

$$w(i, j + 1) + w(i + 1, j) \geq w(i, j) + w(i + 1, j + 1)$$

由于 $x + 1 \leq y + 1 \leq j \leq j + 1$，所以：

$$f[x + 1][j + 1] + f[y + 1][j] \geq f[x + 1][j] + f[y + 1][j + 1]$$

结合这两个不等式，比较 $(1)$ 和 $(2)$，得到：

$$f[i][j + 1] + f[i + 1][j] \geq f[i][j] + f[i + 1][j + 1]$$

证毕。

定理（二维决策单调性）

在状态转移方程 $f[i][j] = min_{i \leq k < j} \lbrace f[i][k] + f[k + 1][j] + w(i, j) \rbrace$ 中（规定 $f[i][i] = w(i, i) = 0$），记 $p[i][j]$ 为令 $f[i][j]$ 取到最小值的 $k$ 值（决策）。

如果 $f$ 满足四边形不等式，那么对于任意 $i < j$，有 $p[i][j - 1] \leq p[i][j] \leq p[i + 1][j]$（二维决策单调性）

证明

为方便起见，记 $p = p[i][j]$，对于任意的 $i < k \leq p$，因为 $f$ 满足四边形不等式：

$$f[i][p] + f[i + 1][k] \geq f[i][k] + f[i + 1][p]$$

移项可得：

$$f[i + 1][k] - f[i + 1][p] \geq f[i][k] - f[i][p]$$

根据 $p$ 的最优性，又有：

$$f[i][k] + f[k + 1][j] \geq f[i][p] + f[p + 1][j]$$

因此：

$(f[i + 1][k] + f[k + 1][j] + w(i + 1, j)) - (f[i + 1][p] + f[p + 1][j] + w(i + 1, j))$

$= (f[i + 1][k] - f[i + 1][p]) + (f[k + 1][j] - f[p + 1][j])$

$\geq (f[i][k] - f[i][p]) + (f[k + 1][j] - f[p + 1][j])$

$= (f[i][k] + f[k + 1][j] - (f[i][p] + f[p + 1][j]))$

$\geq 0$

这意味着对于 $f[i + 1][j]$，$p$ 比任意的 $k \leq p$ 更优，因此 $p[i + 1][j] \geq p[i][j]$

类似地，同理可证 $p[i][j - 1] \leq p[i][j]$

证毕。

根据上面两条定理，我们只需要在 $p[l][r - 1] \leq k \leq p[l + 1][r]$ 的范围内对 $k$ 进行枚举，求出 $f[l][r]$ 和 $p[l][r]$。算法的时间复杂度为 $O(\sum_{l=1}^{N-1} \sum_{r=l+1}^{N} (p[l + 1][r] - p[l][r - 1] + 1)) = O(\sum_{l=1}^{N-1} (p[l + 1][N] - p[1][N - l] + N - l)) = O(N^2)$

可以发现，有外层循环 $l$ 和内层循环 $r$，对于 $f[l][r]$，我们需要枚举决策 $k \in [f[l][r - 1], f[l + 1][r]]$，因此在处理 $f[l][r]$ 之前，要先处理完 $f[l][r - 1]$ 和 $f[l + 1][r]$，我们只需逆序循环 $l$，正序循环 $r$，即可保证递推的正确性。

例题：再探石子合并