四边形不等式优化dp的相关概念

四边形不等式： 设 $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$，都有 $a<a+1\leq c<c+1$，代入定理就会有 $w(a,c+1)+w(a+1,c)\geq w(a,c)+w(a+1,c+1)$

任取 $a+1<c$，都有 $a+1<a+2\leq c<c+1$，代入定理就会有 $w(a+1,c+1)+w(a+2,c)\geq w(a+1,c)+w(a+2,c+1)$

将上述两个不等式相加，再将两边都有的部分消掉，就会得到 $w(a,c+1)+w(a+2,c) \geq w(a,c)+w(a+2,c+1)$

任取 $a+2<c$，都有 $a+2<a+3\leq c<c+1$，代入定理就会有 $w(a+2,c+1)+w(a+3,c) \geq w(a+2,c)+w(a+3,c+1)$

再将这两个不等式相加，就会得到 $w(a,c+1)+w(a+3,c) \geq w(a,c)+w(a+3,c+1)$

到此我们一共得到三个不等式：

$$ w(a,c+1)+w(a+1,c)\geq w(a,c)+w(a+1,c+1) $$

$$ w(a,c+1)+w(a+2,c) \geq w(a,c)+w(a+2,c+1) $$

$$ w(a,c+1)+w(a+3,c) \geq w(a,c)+w(a+3,c+1) $$

可以发现，这三个不等式只有第 $2,3$ 项中的 $a$ 变成了 $a+1,a+2,a+3$，同理，这里我们可以取任意的 $a+k$，这就意味着这里可以取任意一个在 $[a,c]$ 之间的数。

因此任取 $a \leq b \leq c$，都有 $w(a,c+1)+w(b,c) \geq w(a,c)+w(b,c+1)$。

任取 $a \leq b \leq c+1$，都有 $w(a,c+2)+w(b,c+1) \geq w(a,c+1)+w(b,c+2)$。

将两个不等式相加，就会得到 $w(a,c+2)+w(b,c) \geq w(a,c)+w(b,c+2)$

任取 $a \leq b \leq c+2$，都有 $w(a,c+3)+w(b,c+2) \geq w(a,c+2)+w(b,c+3)$

将两个不等式相加，就会得到 $w(a,c+3)+w(b,c) \geq w(a,c)+w(b,c+3)$

到此我们又得到了三个不等式：

$$ w(a,c+1)+w(b,c) \geq w(a,c)+w(b,c+1) $$

$$ w(a,c+2)+w(b,c) \geq w(a,c)+w(b,c+2) $$

$$ w(a,c+3)+w(b,c) \geq w(a,c)+w(b,c+3) $$

可以发现，这三个不等式中只有第 $1,4$ 中的 $c$ 变成了 $c+1,c+2,c+3$，同理，我们这里可以取任意的 $c+k$，这就意味着这里可以取任意一个 $\geq c$ 的数。

因此任取 $a \leq b \leq c \leq d$，都有 $w(a,d)+w(b,c) \geq w(a,c)+w(b,c)$。

综上所述，对于任意一个满足定理的不等式，同样满足四边形不等式，由此证明两种不等式是等价的关系。

一维四边形不等式的性质：

在状态转移方程 $f_i = min_{0 \leq j < i} \lbrace f_j + val(j, i) \rbrace$ 中，函数 $val$ 满足四边形不等式，若 $p$ 对于 $i$，比 $p$ 前面的所有决策都更优，则 $p$ 对于 $i’ > i$ 都有 $p$ 比 $p$ 前面的所有决策更优。

特殊地，对于 $i$ 的最优决策 $p$，同样满足对于 $i’ > i$，都有 $p$ 比 $p$ 前面的所有决策更优，这就意味着 $f_i$ 的最优决策具有单调性。

证明一维四边形不等式的性质：

任取 $0 \leq j < p < i < i’$，此时对于任意的 $j$ 对于 $i$ 而言都不如 $p$ 好，我们需要证明任意的 $j$ 对于 $i’$ 而言也都不如 $p$ 好。

由于此时对于 $i$ 来说 $p$ 比 $j$ 好，则一定满足 $f_p+val(p,i) \leq f_j+val(j,i)$，记为不等式 $1$

而 $val$ 函数满足四边形不等式，因此就有 $val(j,i’)+val(p,i) \geq val(j,i)+val(p,i’)$。

将不等式整理得到 $val(p,i’)-val(p,i) \leq val(j,i’)-val(j,i)$

然后我们将得到的不等式与不等式 $1$ 相加，得到 $f_p+val(p,i’) \leq f_j+val(j,i’)$

这就意味着对于 $i’$ 而言，$p$ 是比 $j$ 好的，由此证明了四边形不等式的性质。

一维四边形不等式的性质的应用：

首先对于所有状态来说，$f_0$ 是我们最开始能确定的，这就意味着最开始已经有了一个决策 $0$。

设 $p_i$ 表示对于 $f_i$ 而言，当前所有决策里面最好的决策是多少。

最开始我们能用的决策只有 $0$，因此最开始所有的 $p_i$ 都是 $0$。

而根据四边形不等式的性质，我们首先可以知道 $p_i$ 一定是单调递增的，因为假如此时 $p_i$ 是 $j$，则意味着此时对于 $f_i$ 来说，$j$ 比前面所有决策都好，因此对于后面任意的 $f_{i’}$ 来说，$j$ 同样比前面所有决策都好，所以 $p_{i’} \geq j$，因此 $p_i$ 一定单调递增。

此时当我们求到 $f_i$ 时，就意味着 $0 \sim i-1$ 这些状态都已经求完了，也就意味着 $0 \sim i-1$ 这些决策都已经考虑到 $p$ 数组中了，此时的 $p_i$ 就是考虑完 $0 \sim i-1$ 之后的最优决策，而对于 $f_i$ 而言我们要考虑的决策只有 $0 \sim i-1$，因此此时 $p_i$ 恰好就是 $f_i$ 最终的最优决策，所以此时 $f_i=f_{p_i}+val(p_i,i)$。

当我们更新完 $f_i$ 之后，$f_i$ 就可能去更新后面的其他状态，因此我们还要看一下决策 $i$ 会更新 $p$ 数组中的哪些状态。我们找到某一个位置，这个位置用 $i$ 会更好，因此我们将这个位置的决策换成 $i$，而这个位置换成 $i$ 后，根据性质后面所有位置都应该换成 $i$，所以我们只需要找出第一个换成 $i$ 更好的位置，将从这个位置往后的所有决策都换成 $i$，这里显然可以通过二分来查找第一个换成 $i$ 的位置。

假设第一个换成 $i$ 的位置是 $x$，则对于 $x$ 前面的位置来说 $i$ 显然不最优的，而对于 $x$ 后面的位置来说 $i$ 都是最优的，整个区间具有两段性，所以我们就可以二分出第一个换成 $i$ 的位置。

当我们找出第一个换成 $i$ 的位置后，我们需要将后面所有位置的决策都换成 $i$，如果我们暴力的去替换，那么时间复杂度还是 $O(n)$ 的，由于 $p$ 数组是非严格单调递增的，因此我们可以一段一段的来存储决策，每一段用三个信息来存，$j,l,r$ 分别表示决策、左端点、右端点，这样就可以 $O(1)$ 的存储决策了。

那么这样存储之后，我们如何找到第一个换成 $i$ 的位置呢，可以将 $p$ 数组看成一个队列，每次从队尾开始找，每次判断一下如果当前这段的开头是 $i$ 最优的话，则整个区间一定都是 $i$ 最优。如果队尾的开头是 $i$ 最优，那么我们就将这个区间删去，直到队尾的开头不是 $i$ 最优，此时我们再看一下队尾的末尾是不是 $i$ 最优，如果是，说明 $i$ 的位置应该在当前这个区间中，那么我们就在区间中二分找出这个位置。二分出这个位置之后，将这个位置往后一整段全部填 $i$ 即可，后面一整段全部填 $i$ 的话，我们只需要加入一个新的区间即可，就不用暴力替换了。对于每个 $i$，我们最多只会加一个区间，每个区间最多只会删除一次，每次二分时间复杂度都是 $O(logn)$，因此每次用 $i$ 更新 $p$ 数组的时间复杂度均摊为 $O(logn)$。

并且在实现的过程中，如果 $f_i$ 已经更新完，则对于 $p_0 \sim p_i$ 就都没有用了，我们就可以将这部分的区间都删掉，这样整个过程就和单调队列很相似，每次去掉无用区间，那么队头就是对于 $i$ 的最优解，把队头取出来算下 $i$，再用 $i$ 更新一下 $p$ 数组，更新完之后再看一下队头有没有越界，越界就删掉，以此类推。可以发现和单调队列的步骤非常相似。

二维四边形不等式

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

$$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$，其中 $w(i,j)$ 满足四边形不等式，且对于任意的 $a \leq b \leq c \leq d$，都有 $w(a,d) \geq w(b,c)$，那么 $f$ 也满足四边形不等式。

证明：

若 $j=i+1$，而对于 $j < i$，都有 $i<i+1 \leq j<j+1$，要想证明 $f$ 满足四边形不等式，就是要证明 $f_{i,j+1}+f_{i+1,j} \geq f_{i,j}+f_{i+1,j+1}$

而 $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}$ 的决策 $k$ 要想满足 $i\leq k<j$，$k$ 就只有 $i$ 和 $i+1$ 两种取值。

当 $k=i$ 时，$f_{i,i+2}=f_{i,i}+f_{i+1,i+2}+w_{i,i+2}=f_{i+1,i+2}+w(i,i+2)$。而对于 $f_{i+1,i+2}$ 决策只能取 $i+1$，因此 $f_{i+1,i+2}=f_{i+1,i+1}+f_{i+2,i+2}+w(i+1,i+2)=w(i+1,i+2)$，因此 $f_{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}$。由此证明 $f_{i,j+1}+f_{i+1,j} \geq f_{i,j}+f_{i+1,j+1}$，四边形不等式成立。

当 $k=i+1$ 时，$f_{i,i+2}=f_{i,i+1}+f_{i+2,i+2}+w(i,i+2)=f_{i,i+1}+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,j+1}+f_{i+1,j} \geq f_{i,j}+f_{i+1,j+1}$，四边形不等式成立。

此时 $j=i+1$，也就是 $j-i=1$ 时，四边形不等式成立，假设 $j-i<k$ 时四边形不等式成立，求证 $j-i=k$ 时四边形不等式也成立。

设 $f_{i,j+1}$ 的最优决策是 $x$，$f_{i+1,j}$ 的最优决策是 $y$。

当 $x \leq 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)$（这里对于两个 $f$ 分别取了其中一个不一定最优的决策 $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)$。

由于 $w$ 满足四边形不等式，因此对于 $i<i+1\leq j<j+1$，就会有 $w(i,j+1)+w(i+1,j) \geq w(i,j)+w(i+1,j+1)$，那么我们接下来只需要证明$f_{i,x}+f_{x+1,j+1}+f_{i+1,y}+f_{y+1,j} \geq f_{i,x}+f_{x+1,j}+f_{i+1,y}+f_{y+1,j+1}$，就能证明满足四边形不等式，我们将左、右相同的两项消去，那么只需要证明 $f_{x+1,j+1}+f_{y+1,j} \geq f_{x+1,j}+f_{y+1,j+1}$ 即可。

由于 $x \geq i$，因此 $x+1 \geq i+1$，而此时 $j-i=k$，所以 $j-(x+1) \leq j-(i+1) < j-i = k$，因此此时对于 $x+1\leq y+1 \leq j<j+1$ 满足四边形不等式，就会有 $f_{x+1,j+1}+f_{y+1,j} \geq f_{x+1,j}+f_{y+1,j+1}$，到此证明四边形不等式成立。

当 $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)$（这里对于两个 $f$ 分别取了其中一个不一定最优的决策 $x,y$），对于不等式右边 $f_{i,j}+f_{i+1,j+1} \leq f_{i,y}+f_{y+1,j}+w(i,j)+f_{i+1,x}+f_{x+1,j+1}+w(i+1,j+1)$。

由于 $w$ 满足四边形不等式，因此对于 $i<i+1 \leq j<j+1$，就会有 $w(i,j+1)+w(i+1,j) \geq w(i,j)+w(i+1,j+1)$，那么我们接下来只需要证明 $f_{i,x}+f_{x+1,j+1}+f_{i+1,y}+f_{y+1,j} \geq f_{i,y}+f_{y+1,j}+f_{i+1,x}+f_{x+1,j+1}$，就能证明满足四边形不等式，我们将左、右相同的两项消去，那么只需要证明 $f_{i,x}+f_{i+1,y} \geq f_{i,y}+f_{i+1,x}$ 即可

由于 $y < j$，此时 $j-i=k$，因此 $y-i < j-i = k$，那么对于 $i<i+1\leq y \leq x$ 满足四边形不等式，就会有 $f_{i,x}+f_{i+1,y} \geq f_{i,y}+f_{i+1,x}$，到此证明四边形不等式成立。

综上所述，通过数学归纳法证明对于任意的 $f_{i,j}$ 都满足四边形不等式。

二维四边形不等式的性质：

在状态转移方程 $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}$ 的最优决策。

若 $f$ 满足四边形不等式，那么对于任意 $i < j$，有 $p_{i,j-1} \leq p_{i,j} \leq p_{i+1,j}$（二维决策单调性）

证明二维四边形不等式的性质：

设 $P = p_{i,j}$，那么对于 $i<i+1 \leq k \leq P$，就会有 $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}$。

我们假设 $k$ 是 $P$ 前面的任意一个决策，则 $\big( f_{i+1,k}+f_{k+1,j}+w(i+1,j) \big) - \big( f_{i+1,P}+f_{P+1,j}+w(i+1,j) \big) = \big( f_{i+1,k}-f_{i+1,P} \big) + \big( f_{k+1,j}+f_{P+1,j} \big) \geq f_{i,k}-f_{i,P}+f_{k+1,j}+f_{P+1,j}$

由于 $P$ 是 $f_{i,j}$ 的最优决策，那么就会有 $f_{i,k}+f_{k+1,j}\geq f_{i,P}+f_{P+1,j}$，整理得到 $f_{i,k}+f_{i,P}+f_{k+1,j}-f_{P+1,j} \geq 0$。

因此证明出 $\big( f_{i+1,k}+f_{k+1,j}+w(i+1,j) \big) - \big( f_{i+1,P}+f_{P+1,j}+w(i+1,j) \big) \geq 0$，这就意味着对于 $f_{i+1,j}$ 而言，$P$ 一定比小于 $P$ 的任何一个决策 $k$ 都要好的，因此 $p_{i+1,j}$ 一定只会取 $P$ 或 $P$ 后面的值，也就意味着 $p_{i+1,j} \geq p_{i,j}$。同理也可证明 $p_{i,j} \geq p_{i,j-1}$，这里不再赘述。

二维四边形不等式的性质的应用:

二维四边形不等式优化其实非常简单，对于正常的区间 $dp$，我们的第三层循环应该是从 $i$ 枚举到 $j-1$，现在由于 $f_{i,j}$ 的决策 $p_{i,j}$ 在 $p_{i,j-1} \sim p_{i+1,j}$ 之间，因此我们直接将第三层循环从 $p_{i,j-1}$ 枚举到 $p_{i+1,j}$，这样时间复杂度就神奇地从 $O(n^3)$ 降为 $O(n^2)$ 了。

这里的证明需要去矩阵上进行验证，首先 $i \leq j$，因此所有有效的状态 $f_{i,j}$ 一定是矩阵的对角线及以上的所有位置，这些状态刚好构成一个上三角矩阵。

然后对于每个状态 $f_{i,j}$，我们需要枚举 $p_{i,j-1} \sim p_{i+1,j}$，因此枚举的数量就是 $p_{i+1,j}-p_{i,j-1}+1$，然后我们统计一下所有状态的总枚举数是多少。

观察每个状态的对时间的贡献，对于 $f_{i,j}$，它左边的格子是用来减去的，是负贡献，它下面的格子是用来加上的，是正贡献，剩下的 $1$ 我们单独提出来考虑，每个状态都有 $1$ 的贡献，状态数量是 $O(n^2)$ 级别的，因此所有状态的 $1$ 的总贡献就是 $O(n^2)$ 的。

对于每个状态，如果它的右边有状态，则它就会被用来做一次负贡献，如果它的上面有状态，则它就会被用来做一次正贡献，因此一个状态如果右边和上面都有状态，则它会被做一次负贡献，再做一次正贡献，正负相抵，那么这些状态的贡献就会清零。

真正存在贡献的只有右边或上面有一边没有状态的这些状态。可以发现这些状态就是最上边的状态以及最右边的状态。

对于最上边的状态，每个状态只会被它右边的状态用来做负贡献，对于最右边的状态，每个状态只会被它上面的状态用来做正贡献。因此真正的贡献其实就是最右边的数减去最上边的数，最右边有 $n$ 个数，每个数 都是 $O(n)$，所以是 $O(n^2)$ 的，最上边也同理，因此整理的贡献就是 $O(n^2)-O(n^2)$，然后再加上 $1$ 的贡献，也是 $O(n^2)$ 的，因此整个的时间复杂度就是 $O(n^2)$ 的。