四边形不等式学习笔记

heffo_hard · 2026-06-17 21:11:07 · 算法·理论

在区间 dp 中，经常会出现这样的转移方程：

\min_{i\le k<j}({dp_{i,k},dp_{k+1,j}+w(i,j)}) & i<j\\ 0 & i=j \\ \infty & i>j\\ \end{cases}

定义

此时如果 i\le i' \le j \le j' 并且有：

w(i,j)+w(i',j')\le w(i,j')+w(i',j)

那么称函数 w 满足四边形不等式。
可以得到两个定理：

定理 1

此时 dp 满足四边形不等式。即 dp_{i,j}+dp_{i',j'}\le dp_{i,j'}+dp_{i',j}。 :::info[证明]

i<i'=j<j'
此时原不等式变为 dp_{i,j}+dp_{j,j'}\le dp_{j,j}+dp_{i,j'}=dp{i,j'}。
设 k=\max(t\mid dp_{i,j'}=dp_{i,t-1}+dp_{t,j'}+w(i,j'))。（k 其实就是 dp_{i,j'} 的最优决策点）
不妨设 k \le j（可由对称性得）。
\because dp_{i,j'}=dp_{i,t-1}+dp_{t,j'}+w(i,j') dp_{i,j}+dp_{j,j'} & \le w(i,j)+dp_{i,k-1}+dp_{k,j}+dp_{j,j'}\\ & \le w(i,j')+dp_{i,k-1}+dp_{k,j}+dp_{j,j'}\\ & \le w(i,j')+dp_{i,k-1}+dp_{k,j'}\\ & = dp_{i,j'}\\ \end{aligned}
i<i'<j<j'
设
y=\max(t\mid dp_{i',j}=\max(w_{i',j}+dp_{i',t-1}+dp_{t,j}))\\ z=\max(t\mid dp_{i,j'}=\max(w_{i,j'}+dp_{i,t-1}+dp_{t,j'}))\\ \end{cases}
（y 为 dp_{i',j} 的最优决策点，z 为 dp_{i,j'} 的最优决策点）同理，不妨设 z\le y，由定义知 i<z\le y\le j。因此有：
dp_{i,j}+dp_{i',j'}&\le w(i,j)+dp_{i,z-1}+dp_{z,j}+w(i',j')+dp_{i',y-1}+dp_{y,j'}\\ &\le w(i,j')+w(i',j)+dp_{i',y-1}+dp_{i,z-1}+dp_{z,j}+dp_{y,j'}\\ &\le w(i,j')+w(i',j)+dp_{i',y-1}+dp_{i,z-1}+dp_{y,j}+dp_{z,j'}\\ &=dp_{i,j'}+dp_{i',j}\\ \end{aligned}
证毕。 :::

定理 2

定义 s_{i,j} 为 dp_{i,j} 的最优决策点，那么有 s_{i,j} 单调，即：
s_{i,j}\le s_{i,j+1}\le s_{i+1,j+1}
:::info[证明] 由对称性，仅证 s_{i,j}\le s_{i,j+1}。
i<j
令 dp_{k,i,j} 为 dp_{i,k-1}+dp_{k,j}+w(i,j)。
$$dp_{k,j}+dp_{k',j+1}\le dp_{k',j}+dp_{k,j+1}$$。两边同时加上 $w(i,j)+dp_{i,k-1}+w(i,j+1)+dp_{i,k'-1}$，得： $\begin{aligned} & dp_{k,i,j}+dp_{k',i,j+1}\le dp_{k,i,j+1}+dp_{k',i,j} \iff \\ & dp_{k,i,j}-dp_{k',i,j} \le dp_{k,i,j+1}-dp_{k',i,j+1} \end{aligned}
可以发现：
dp_{k,i,j}\le dp_{k',i,j} \to dp_{k,i,j+1}\le dp_{k',i,j}
又 \because k' \ge k，同时对于所有的 k<s_{i,j}，有 dp_{s_{i,j},i,j}=dp_{i,j}\le dp_{k,i,j}。
::: 根据定理 2，原转移方程变为： $$dp_{i,j} = \begin{cases} \min_{s_{i,j-1}\le k\le s_{i+1,j}}({dp_{i,k},dp_{k+1,j}+w(i,j)}) & i<j\\ 0 & i=j \\ \infty & i>j\\ \end{cases}$$ 原来转移的时间复杂度为 $\mathcal{O}(n^3)$，而现在的时间复杂度为： $\begin{aligned} \mathcal{O}\left(\sum_{l=2}^{n}\sum_{i=1}^{n+1-l}(1+s_{i+1,i+l-1}-s_{i,i+l-2})\right)&=\mathcal{O}\left(\sum_{l=2}^{n}(n+1-l+s_{n+2-l,n}-s_{1,l-1})\right)\\ &\le \mathcal{O}\left(\sum_{l=2}^{n}(2 \times n+2 \times l -1)\right)\\ &=\mathcal{O}\left((n-1)^2\right)\\ \end{aligned}
即时间复杂度为 \mathcal{O}(n^2)。
实际上四边形不等式的应用并不局限于上面的式子。

例题

P4767 [IOI 2000] 邮局加强版
如果没有做过的话建议先做一下原始版：P10967 [IOI 2000] 邮局（原始版）
代码如下：
```
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define pref static inline
#define fi first
#define se second
using namespace std;
const int MAXN=305;
int n,p,a[MAXN],dis[MAXN][MAXN],dp[MAXN][MAXN];
namespace heffo_hard{
pref void solve(){
    cin>>n>>p;
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a+1,a+1+n);//排序（放置到轴上）
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            for(int k=i;k<=j;++k){
                dis[i][j]+=abs(a[k]-a[(i+j)>>1]);
            }
        }
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;++i)dp[1][i]=dis[1][i];
    for(int i=2;i<=p;++i){
        for(int j=i;j<=n;++j){
            for(int k=i-1;k<j;++k){
                dp[i][j]=min(dp[i][j],dp[i-1][k]+dis[k+1][j]);
            }
        }
    }
    cout<<dp[p][n];
}
};
```

signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); heffo_hard::solve(); return 0; } / heffo_hard 定义dis[i][j]:考虑在[i,j]中放置1个邮局的最小距离和（在中间放置）所以dis[i][j]=bs(a[k]-a[(i+j)>>1]); /

但是现在这份代码过不了，时间复杂度为 $\mathcal{O}(PV^2)$，用什么优化呢？四边形不等式！  
发现 dis 是满足四边形不等式的，所以我们可以对 $k$  的取值范围进行优化，优化完的代码如下：
```cpp
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define pref static inline
#define fi first
#define se second
using namespace std;
int n,p,a[3005],dis[3005][3005],dp[3005][305],s[3005][305];
namespace heffo_hard{
    pref void solve(){
        cin>>n>>p;
        for(int i=1;i<=n;++i){
            cin>>a[i];
        }
        sort(a+1,a+1+n);//排序（放置到轴上）
        for(int i=1;i<=n;++i){
            dis[i][i]=0;
            for(int j=i+1;j<=n;++j){
                int mid=(i+j)>>1;
                dis[i][j]=dis[i][j-1]+a[j]-a[mid];
            }
        }

        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;++i){
            dp[i][1]=dis[1][i];
            s[i][1]=0;
        }
        for(int j=2;j<=p;++j){
            s[n+1][j]=n;
            for(int i=n;i>=j;--i){
                for(int k=s[i][j-1];k<=min(i-1,s[i+1][j]);++k){
                    int tmp=dp[k][j-1]+dis[k+1][i];
                    if(tmp<dp[i][j]){
                        dp[i][j]=tmp;
                        s[i][j]=k;
                    }
                }
            }
        }
        cout<<dp[n][p];
    }
};

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    heffo_hard::solve();
    return 0;
}
/*
heffo_hard
定义dis[i][j]:考虑在[i,j]中放置1个邮局的最小距离和（在中间放置）
所以dis[i][j]=bs(a[k]-a[(i+j)>>1]);
*/

现在的时间复杂度是 \mathcal{O}(PV)，可以通过本题。
制作不易，可以点个 star 吗？
如果有问题欢迎评论。

四边形不等式学习笔记

定义

定理 1

定理 2

例题