四边形不等式优化dp
wanjiabao
·
·
算法·理论
致歉
在诸位谷民的努力之下，我找出了一堆 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) 的转移式：
注意到（~~注意力惊人~~）$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] 邮局 加强版](https://www.luogu.com.cn/problem/P4767)（注意求 $cost$ 要用中位数）
[HDU2829 Lawrence](https://vjudge.net/problem/HDU-2829)
~~别问我为什么不讲因为我不会证~~
## 总结
四边形不等式优化属实是最难的一种 dp 优化，真正的在考场上我们不一定有时间严格证明。再者，这一类题目的 dp 部分往往是千篇一律，但 $cost$ 的求法千奇百怪。所以我们需要多练习，尽量形成一种直觉。同时，像所有动态规划一样，**一定要注意初始化和数据范围**。
# 终于结束了！