四边形不等式优化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$ 的求法千奇百怪。所以我们需要多练习,尽量形成一种直觉。同时,像所有动态规划一样,**一定要注意初始化和数据范围**。
# 终于结束了!