四合院${}_{\text{儿}}$$_儿$不等式

前言

本文翻自此处。有补充和省略。

记 $A\prec B$$A≺B$ 为 $A$$A$ 严格优于 $B$$B$ 。 ($⪯$$⪯$ 类似)

注: quadrangle 又译 四合院${}_{\text{儿}}$$_儿$

四合院${}_{\text{儿}}$$_儿$不等式

对于花费函数 $C(l,r)$$C(l,r)$ 当且仅当 $C(a,c)+C(b,d)⪯C(a,d)+C(b,c)$$C(a,c)+C(b,d)⪯C(a,d)+C(b,c)$ 时称它满足四合院${}_{\text{儿}}$$_儿$不等式。

记 $opt(r)$$opt(r)$ 为最靠右的最优的 $C(l,r)$$C(l,r)$ 的 $l$$l$ 。

称满足四合院${}_{\text{儿}}$$_儿$性质为“四合院${}_{\text{儿}}$$_儿$友好”。

Array Partition DP

考虑一种动规: 将数组 $a$$a$ 划分为 $k$$k$ 段(交为空集且并为全集)。

显然有 $dp$$dp$ 方程如下。

$dp[0][0]=0$$dp[0][0]=0$

$dp[i][0]=dp[0][k]=\infty$$dp[i][0]=dp[0][k]=∞$ $(i,k\ge 1)$$(i,k≥1)$

$dp[i][k]=mi{n}_{1\le j\le i}dp[j-1][k-1]+C(j,i)$$dp[i][k]=min_{1≤j≤i}{dp[j−1][k−1]+C(j,i)}$ $(i,k\ge 1)$$(i,k≥1)$

FACT1

若 $C()$$C()$ 是四合院${}_{\text{儿}}$$_儿$友好的，那么 $opt()$$opt()$ 不减。

证明:画图易得。

假设 $opt()$$opt()$ 单减，那么有 $b\prec d,a\prec c$$b≺d,a≺c$

那么有 $a+b\prec c+d$$a+b≺c+d$ ，然而实际上 $c+d\prec a+b$$c+d≺a+b$ 故矛盾。

FACT2

记 $f_k(l,r)=dp[l-1][k-1]+C(l,r)$$f_k(l,r)=dp[l-1][k-1]+C(l,r)$ ，若 $C()$$C()$ 四合院友好(简写为 $QF$$QF$ )，那么 $f_k()$$f_k()$ 也 $QF$$QF$。

证明: 对于$a\le b\le c\le d$$a≤b≤c≤d$ $f_k(a,c)+f_k(b,d)=dp[a-1][k-1]+dp[b-1][k-1]+C(a,c)+C(b,d)$$f_k(a,c)+f_k(b,d)=dp[a−1][k−1]+dp[b−1][k−1]+C(a,c)+C(b,d)$ $⪯dp[a-1][k-1]+dp[b-1][k-1]+C(a,d)+C(b,c)=f_k(a,d)+f_k(b,c).\square$$⪯dp[a−1][k−1]+dp[b−1][k−1]+C(a,d)+C(b,c)=f_k(a,d)+f_k(b,c). □$

FACT3

记 $op{t}_k(r)$$opt_k(r)$ 为对于 $k$$k$ ，$r$$r$ 最优的 $f_k(l,r)$$f_k(l,r)$ 的决策点 $l$$l$ 。

若有 $C()$$C()$ 满足 $QF$$QF$ ，那么有 $op{t}_k(r)\le op{t}_{k+1}(r)$$opt_k(r)≤opt_{k+1}(r)$ 。

证明:

对于 $k$$k$ 的一种划分 $I$$I$ ，$dp[r][k]:[a_k,d_k],...,[a_1,d_1]$$dp[r][k]: [a_k,d_k],...,[a_1,d_1]$ ，

在 $k+1$$k+1$ 时有另一种划分 $II$$II$ ， $dp[r][k+1]:[b_{k+1},c_{k+1}],...[b_1,c_1]$$dp[r][k+1]:[b_{k+1},c_{k+1}],...[b_1,c_1]$

利用反证法，若 $op{t}_{k+1}(r)<op{t}_k(r)$$opt_{k+1}(r)<opt_k(r)$，即 $a_1>b_1$$a_1>b_1$ ，同时 $a_k<b_k$$a_k<b_k$

那么在中间一定有一个在 $II$$II$ 中的划分满足在 $I$$I$ 中的对于恰好包含它。

假设黄色是 $I$$I$ ，绿色的第一个是 $II$$II$ 。那么有绿色第一个由于绿色第二个。(因为绿色第一个是最优化分)

对于绿色的两个，同时合上 $a,b$$a,b$ 那一段，由四边形不等式得到蓝色的不等关系。

然而，这意味着黄色的不是一种最优划分，因此有矛盾。证完。

SUMMARY

综上，对于这种类型的 $dp$$dp$ 我们有 $op{t}_{k-1}(r)\le op{t}_k(r)\le op{t}_k(r+1)$$opt_{k-1}(r)≤opt_{k}(r)≤opt_{k}(r+1)$

Array Merging DP:

对于类似石子合并的动态规划，我们有类似于以下的 $dp$$dp$ 方程。

$dp[l][l]=C(l,l)$$dp[l][l]=C(l,l)$ $dp[l][r]=C(l,r)+mi{n}_{l\le m<r}\{dp[l][m]+dp[m+1][r]\}$$dp[l][r]=C(l,r)+min_{l≤m<r}\{dp[l][m]+dp[m+1][r]\}$

FACT4[1]

定义 $opt(l,r)$$opt(l,r)$ 为最靠右的决策最优点使得 $dp[l][r]=C(l,r)+dp[l][m]+dp[m+1][r]$$dp[l][r]=C(l,r)+dp[l][m]+dp[m+1][r]$。

移项，并且设 $f_l(r)=dp[l][r]-C(l,r)$$f_l(r)=dp[l][r]-C(l,r)$。

通 FACT2 ，我们固定 $f$$f$ 的左端点，那么有 $opt(l,r)\le opt(l,r+1)$$opt(l,r)≤opt(l,r+1)$。

FACT5

若 $C()$$C()$ 有 $QF$$QF$ 那么 $dp()$$dp()$ 也是 $QF$$QF$ 。

我们按长度从小到大递推。

首先长度为 1 的默认满足。

对于 $dp[a][c]+dp[b][d]+C(a,c)+C(b,d)$$dp[a][c]+dp[b][d]+C(a,c)+C(b,d)$ 与 $dp[a][d]+dp[b][c]+C(a,d)+C(b,c)$$dp[a][d]+dp[b][c]+C(a,d)+C(b,c)$

我们展开得到:

$LEFTdp[a][c^{\prime }]+dp[c^{\prime }+1][c]+dp[b][d^{\prime }]+dp[d^{\prime }+1][d]+C(a,c)+C(b,d)$$LEFT\ dp[a][c']+dp[c'+1][c]+dp[b][d']+dp[d'+1][d]+C(a,c)+C(b,d)$

$RHGTdp[a][d^{\prime }]+dp[d^{\prime }+1][d]+dp[b][c^{\prime }]+dp[c^{\prime }+1][c]+C(a,d)+C(b,c)$$RHGT\ dp[a][d']+dp[d'+1][d]+dp[b][c']+dp[c'+1][c]+C(a,d)+C(b,c)$

消去相同的项，那么变为:

$LEFTdp[a][c^{\prime }]+dp[b][d^{\prime }]+C(a,c)+C(b,d)$$LEFT\ dp[a][c']+dp[b][d']+C(a,c)+C(b,d)$

$RHGTdp[a][d^{\prime }]+dp[b][c^{\prime }]+C(a,d)+C(b,c)$$RHGT\ dp[a][d']+dp[b][c']+C(a,d)+C(b,c)$

对于 $C()$$C()$ 项，我们有四边形不等式可以证明。

而对于带 “ ' ” 的项，我们有 $FACT4[1]$$FACT4[1]$ 得到决策点自低向高移动，那么 $c^{\prime }<=d^{\prime }$$c'<=d'$。

因此 $dp$$dp$ 项也得到了证明。

FACT4[2]

同理 FACT3 ，固定右端点，那么 $opt(l-1,r)\le opt(l,r)$$opt(l-1,r)≤opt(l,r)$。

SUMMARY

综上所述，对于这类动态规划问题，依然有

$opt(l-1,r)<=opt(l,r)<=opt(l,r+1)$$opt(l-1,r)<=opt(l,r)<=opt(l,r+1)$

如有错误欢迎指正。