四边形不等式问题详解
四边形不等式
设 $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]$,我们执行以下操作:
- 检查队头:设队头为 $(j_0, l_0, r_0)$,若 $r_0 = i - 1$,删除队头,否则令 $l_0 = i$
- 取队头保存的 $j$ 为最优决策,执行状态转移,计算出 $f[i]$
- 尝试插入新决策 $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)$ 插入队尾
二维区间 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$,即可保证递推的正确性。
二维区间 DP 定理证明那里应该是设 $f[i][j-1]$ 以 $x$ 为最优决策吧
是 $+1$ 的,因为这里的证明其实也是证明四边形不等式的第二种形式,即 $w(a+1,b)+w(a,b+1)\geq w(a,b)+w(a+1,b+1)$,可以把 $f[i][j]$ 看成 $w(i,j)$