AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

四边形不等式问题详解

作者: 作者的头像   小小_88 ,  2022-09-21 23:20:18 ,  所有人可见 ,  阅读 303


4


四边形不等式问题详解

四边形不等式

设 $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$ 的情况如下图所示:

图1.png

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

图2.png

直接修改一个数组效率当然很低,因此我们可以建立一个队列,代替 $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$,即可保证递推的正确性。

例题:再探石子合并

2 评论


用户头像
懵逼自动机   1个月前         踩      回复

二维区间 DP 定理证明那里应该是设 $f[i][j-1]$ 以 $x$ 为最优决策吧

用户头像
小小_88   1个月前         踩      回复

是 $+1$ 的,因为这里的证明其实也是证明四边形不等式的第二种形式,即 $w(a+1,b)+w(a,b+1)\geq w(a,b)+w(a+1,b+1)$,可以把 $f[i][j]$ 看成 $w(i,j)$


你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息