四边形不等式优化dp

· · 算法·理论

致歉

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

对各位谷民造成了误导,在此诚挚道歉,希望大家能够学好四边形不等式,再来 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)

我们定义 opt(l,r) 为区间 [l,r] 的最优决策点,也即使 dp(l,r)=dp(l,k)+dp(k+1,r)+cost(l,r)k 值。

引理 1

对于任意 l\leq k\leq rdp(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)=popt(l',r')=q(l\leq p<r,l'\leq q<r)

引理 3

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