致歉

在诸位谷民的努力之下，我找出了一堆 bug，主要是以下两个：

引理 2 的证明完全错了。
发明人姚储枫写成了姚期智（我怎么只知道姚期智啊啊啊）
有两处 $l\leq l'\leq r'\leq r$ 写成 $l\leq l \leq r'\leq r$ 了。

对各位谷民造成了误导，在此诚挚道歉，希望大家能够学好四边形不等式，再来 hack 我的文章！谢谢！

谨以此文纪念全班证明了一个下午才勉强搞懂的神仙 dp 优化。

前置知识：区间 dp。

简介

四边形不等式优化 dp, 由高德纳与姚储枫发现并证明，故学名为 Knuth-Yao Speedup。最初发明这个算法的动机，是为了解决最佳二叉搜索树 (Optimal Binary Search Tree) 问题。四边形不等式优化 dp 属于非常难的 dp 优化，证明极其困难。

问题描述

我们可以将问题简化为解决一类动态规划问题，状态转移如下：

dp(l,r) = \begin{cases} \begin{aligned} & \min_{k \in[l,r)} \{dp(l,k)+dp(k+1,r)+cost(l,r)\},l < r \\ & 0,l=r\\ & \infty,l>r \end{aligned} \end{cases}

其中

dp(l,r)

代表状态，

cost(l,r)

代表转移代价。

暴力

显然，我们可以直接进行区间 dp, 分别遍历

l

r

k

。因为每一层都与

n

同阶，所以时间复杂度为

O(n^3)

。

四边形不等式

玄学的部分来了！

当

cost(l,r)

满足下列条件时，可以使用四边形不等式将时间复杂度从

O(n^3)优化到O(n^2)

：

对于任意的 $l\leq l'\leq r'\leq r$ , $cost(l',r')\leq cost(l,r)$ （包含单调性）
对于任意的 $l\leq l'\leq r'\leq r$ , $cost(l,r')+cost(l',r)\leq cost(l,r)+cost(l',r')$ （四边形不等式）

我们定义

opt(l,r)

为区间

[l,r]

的最优决策点，也即使

dp(l,r)=dp(l,k)+dp(k+1,r)+cost(l,r)

的

k

值。

引理 1

对于任意

l\leq k\leq r

，

dp(l,r)\leq dp(l,k)+dp(k+1,r)+cost(l,r)

。

证明

~~这还需要证明吗~~

显然，由定义可得，当

l<r

时，

dp(l,r)=\min_{k \in[l,r)} \{dp(l,k)+dp(k+1,r)+cost(l,r)\}

；当

l=r

时，

dp(l,r)=0

。所以得证。

引理 2

若

cost(l,r)

满足包含单调性和四边形不等式，则

dp(l,r)

亦满足四边形不等式。即对于任意的

l\leq l'\leq r'\leq r

dp(l,r')+dp(l',r)\leq dp(l,r)+dp(l',r')

。

证明

假设我们已经证明所有

j-i+1<r-l+1

时的

dp(i,j)

都满足四边形不等式。

令

opt(l,r)=p

，

opt(l',r')=q

。

(l\leq p<r,l'\leq q<r)

当 $l'\leq p\leq r'$ 时

不妨设 $p\leq q$ 。

由定义：

$dp(l,r)+dp(l',r')=dp(l,p)+dp(p+1,r)+cost(l,r)+dp(l',q)+dp(q+1,r)+cost(l',r')$

由于已经证明所有 $j-i+1<r-l+1$ 时的 $dp(i,j)$ 都满足四边形不等式，所以可得：

$dp(p+1,r)+dp(q+1,r')\geq dp(p+1,r')+dp(q+1,r)$

又因为 $cost(l,r)$ 满足四边形不等式，有：

$cost(l,r)+cost(l',r')\geq cost(l,r')+cost(l',r)$

原式变形为：

$dp(l,r)+dp(l',r')\geq dp(l,p)+dp(p+1,r)+cost(l,r')+dp(l',q)+dp(q+1,r)+cost(l',r)$

由引理 1 化为：

$dp(l,r)+dp(l',r')\geq dp(l,r')+dp(l',r)$

对于 $p\geq q$ 的证明大同小异。
当 $p<l'$ 时

由定义：

$dp(l,r)+dp(l',r')=dp(l,p)+dp(p+1,r)+cost(l,r)+dp(l',r')$

由于已经证明所有 $j-i+1<r-l+1$ 时的 $dp(i,j)$ 都满足四边形不等式，所以可得：

$dp(p+1,r)+dp(l',r')\geq dp(p+1,r')+dp(l',r)$

原式变形为：

$dp(l,r)+dp(l',r')\geq dp(l,p)+dp(p+1,r')+cost(l,r)+dp(l',r)$

又由于 $cost(l,r)$ 满足包含单调性，所以可得：

$cost(l,r)\geq cost(l,r')$

原式变形为：

$dp(l,r)+dp(l',r')\geq dp(l,p)+dp(p+1,r')+cost(l,r')+dp(l',r)$

由引理 1 得：

$dp(l,r)+dp(l',r')\geq dp(l,r')+dp(l',r)$
对于 $p>r'$ 的情况，与上一种大同小异，这里不再赘述，请读者自行证明。

引理 3

对于任意

l<r

，

opt(l,r-1)\leq opt(l,r)\leq opt(l+1,r)

证明

我们先证明前半部分：

opt(l,r-1)\leq opt(l,r)

反证法。令

p=opt(l,r-1),q=opt(l,r)

，设

p>q

。

(l\leq p<r-1,l\leq q<r)

由

p=opt(l,r-1),q=opt(l,r)

，得：

dp(l,p)+dp(p+1,r-1)\leq dp(l,q)+dp(q+1,r-1)

dp(l,q)+dp(q+1,r)\leq dp(l,p)+dp(p+1,r)

两式相加，得：

dp(l,p)+dp(l,q)+dp(p+1,r-1)+dp(q+1,r)\leq dp(l,p)+dp(l,q)+dp(q+1,r-1)+dp(p+1,r)

显然可以将两边都有的

dp(l,p)+dp(l,q)

去掉，得：

dp(p+1,r-1)+dp(q+1,r)\leq dp(q+1,r-1)+dp(p+1,r)

由于

q+1<p+1\leq r-1<r

，而

dp(l,r)

满足四边形不等式，所以：

dp(q+1,r-1)+dp(p+1,r)\leq dp(p+1,r-1)+dp(q+1,r)

矛盾，所以

opt(l,r-1)\leq opt(l,r)

。

对后半部分：

opt(l,r)\leq opt(l+1,r)

的证明过程大同小异。

发现

由于

opt(l,r-1)\leq opt(l,r)\leq opt(l+1,r)

，所以当我们遍历

k

时，只需要遍历

opt(l,r-1)

到

opt(l+1,r)

就可以了！

时间复杂度

\begin{align*} & O(\sum_{1\leq l<r\leq n}(opt(l+1,r)-opt(l,r-1)+1)) \\ & = O(\sum^{n}_{len=2}\sum^{n-len+1}_{i=1}opt(i+1,i+len-1)-opt(i,i+len-2)+1) \\ & = O(\sum^{n}_{len=2}((n-len+1)+opt(n-len+2,n)-opt(1,len-1)) \\ & = O(n^2) \\ \end{align*}

Ohhhhhhh 太逆天了！

例题

SP15736 BRKSTRNG - Breaking String

我们很快列出一个

O(n^3)

的转移式：

dp_{l,r}=\min_{k=l}^r dp_{l,k}+dp_{k+1,r}+c_r-c_{l-1}

（这里

c_i

指第

i

个断点的位置，单调递增）

注意到（~~注意力惊人~~）

cost(l,r)

（即

c_r-c_{l-1}

）满足四边形不等式，证明如下：

对于任意正整数

l\leq l'\leq r'\leq r

，有：

cost(l,r')+cost(l',r)=c_{r'}-c_{l-1}+c_r-c_{l'-1}=c_r-c_{l-1}+c_{r'}-c_{l'-1}=cost(l,r)+cost(l',r')

，满足四边形不等式。

证毕。

所以说我们在枚举

k

时只需要枚举从

opt_{l,r-1}

到

opt_{l+1,r}

就可以了。

CPP

#include<bits/stdc++.h>
#define int  long long
using namespace std;
int len,n,c[1005],dp[1005][1005],g[1005][1005];
signed main(){
	while(cin>>len>>n){
		c[n+1]=len;
		for(int i=1;i<=n;i++){
			cin>>c[i];
		}
		memset(dp,0x3f,sizeof dp);
		for(int i=1;i<=n+1;i++)dp[i][i-1]=0,dp[i][i]=c[i+1]-c[i-1],g[i][i]=i;
		for(int cnt=2;cnt<=n;cnt++){
			for(int l=1;l+cnt-1<=n;l++){
				int r=l+cnt-1;
				for(int k=g[l][r-1];k<=g[l+1][r];k++){
					if(dp[l][r]>dp[l][k-1]+dp[k+1][r]+(c[r+1]-c[l-1])){
						dp[l][r]=dp[l][k-1]+dp[k+1][r]+(c[r+1]-c[l-1]);
						g[l][r]=k;
					}
				}
			}
		}
		cout<<dp[1][n]<<endl;
	}
}

其他例题：

P4767 [IOI2000] 邮局加强版（注意求

cost

要用中位数）

HDU2829 Lawrence

~~别问我为什么不讲因为我不会证~~

总结

四边形不等式优化属实是最难的一种 dp 优化，真正的在考场上我们不一定有时间严格证明。再者，这一类题目的 dp 部分往往是千篇一律，但

cost

的求法千奇百怪。所以我们需要多练习，尽量形成一种直觉。同时，像所有动态规划一样，一定要注意初始化和数据范围。

四边形不等式优化dp

文章操作

致歉