四边形不等式学习笔记

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

$$ dp_(i,j) = \begin{cases} \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 ≤ i^′ ≤ j ≤ j^′ 并且有： w(i, j) + w(i^′, j^′) ≤ w(i, j^′) + w(i^′, j) 那么称函数 w 满足四边形不等式。
可以得到两个定理：

定理 1

此时 dp 满足四边形不等式。即 dp(i, j) + dp(i^′, j^′) ≤ dp(i, j^′) + dp(i^′, j)。

证明

• i = i^′ 或 j = j^′，w(i, j) + w(i^′, j^′) = w(i, j^′) + w(i^′, j)，显然成立。
• i < i^′ = j < j^′ 此时原不等式变为 dp_i, j + dp_j, j^′ ≤ dpj, j + dp_i, j^′ = dpi, j^′。
  设 k = max (t|dp_i, j^′ = dp_{i, t − 1} + dp_t, j^′ + w(i, j^′))。（k 其实就是 dp_i, j^′ 的最优决策点）
  不妨设 k ≤ j（可由对称性得）。
  ∵dp_i, j^′ = dp_{i, t − 1} + dp_t, j^′ + w(i, j^′)
  $\begin{aligned} 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^′
  设
  $\begin{cases} y=\max(t|dp_{i',j}=\max(w_{i',j}+dp_{i',t-1}+dp_{t,j}))\\ z=\max(t|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 ≤ y，由定义知 i < z ≤ y ≤ j。因此有： $\begin{aligned} 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 ≤ s_{i, j + 1} ≤ s_{i + 1, j + 1}

证明

由对称性，仅证 s_i, j ≤ s_{i, j + 1}。

• i > j，s_i, j = s_{i, j + 1} = ∞，显然成立。
• i = j，s_i, j = 0 ≤ s_{i, j + 1}，同样成立。
• i < j
  令 dp_k, i, j 为 dp_{i, k − 1} + dp_k, j + w(i, j)。
  ∴ 对于任意的 k ≤ k^′ ≤ j，有： dp_k, j + dp_{k^′, j + 1} ≤ dp_k^′, j + dp_{k, j + 1}。
  两边同时加上 w(i, j) + dp_{i, k − 1} + w(i, j + 1) + dp_{i, k^′ − 1}，得： $ $
  可以发现：
  dp_k, i, j ≤ dp_{k^′, i, j} → dp_{k, i, j + 1} ≤ dp_{k^′, i, j} 又 ∵k^′ ≥ k，同时对于所有的 k < s_i, j，有 dp_{si, j, i, j} = dp_i, j ≤ dp_k, i, j。
  ∴ dp_{si, j, i, j} ≤ dp_k, i, j，因此 s_{i, j + 1} ≤ s_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} $$ 原来转移的时间复杂度为 𝒪(n³)，而现在的时间复杂度为：
  $ $
  即时间复杂度为 𝒪(n²)。
  实际上四边形不等式的应用并不局限于上面的式子。

例题

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]);
*/

但是现在这份代码过不了，时间复杂度为 𝒪(PV²)，用什么优化呢？四边形不等式！ 发现 dis 是满足四边形不等式的，所以我们可以对 k 的取值范围进行优化，优化完的代码如下：

#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
*/

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