四边形不等式学习笔记

_sin_ · 2023-01-10 19:37:01 · 个人记录

一、什么是四边形不等式

四边形不等式是一种优化动态规划的方式，一般用于区间 dp 。

首先，在区间 dp 的问题中，经常用到一种状态转移方程：

f_{l,r} = \min^{r-1}_{k=l}\{f_{l,k}+f_{k+1, r}\}+w(l,r) \{1\le l < r \le n\}

如果直接转移的话复杂度会达到 O(n^3) ，但是在一些情况下，可以通过四边形不等式优化做到 O(n^2) 。

二、怎么证明可以使用四边形不等式

对于所有题目，四边形不等式需要证明才能使用。~~当然考场上你可以打表或者靠感觉~~

一道区间 dp 题，你写出朴素做法的状态转移方程后，如果 w(l,r) 函数满足这两个性质的话就可以使用四边形不等式优化。

区间包含单调性：如果对于任意 l \le l' \le r' \le r ，均有 w(l',r') \le w(l,r) 成立，则称函数 w 对于区间包含关系具有单调性。
四边形不等式：如果对于任意 l_1 \le l_2 \le r_1 \le r_2 ，均有 w(l_1,r_1) + w(l_2, r_2)\le w(l_1, r_2)+w(l_2, r_1) 成立，则称函数 w 满足四边形不等式（简记为“交叉小于包含”）。若等号永远成立，则称函数 w 满足 四边形恒等式。

证明可以参考 oi-wiki

三、四边形不等式的应用

首先，我们需要一个数组 pos_{l,r} 来记录区间 [l,r] 中的最优决策点，根据四边形不等式可知 pos_{l,r-1} \le pos_{l,r} \le pos_{l+1, r} 。于是时间复杂度降到了 O(n^2) 。

证明可以参考 oi-wiki

四、例题讲解

P4767 [IOI2000]邮局

首先，我们可以推出朴素做法的状态转移方程：

f_{i,j} = \min^{k < i}_{k=0}\{f[k][j-1]+w[k+1][i]\}

然后， w[k+1][i] 是可以预处理出来的，并且 w[k+1][i] 满足四边形不等式的两个性质，所以可以使用四边形不等式优化。

记 pos_{l,r} 为区间 [l,r] 中的最优决策点，由四边形不等式可知 pos_{l,r-1} \le pos_{l,r} \le pos_{l+1, r} 。时间复杂度降到了 O(n^2) 。可以通过本题。

示例代码：

#include <bits/stdc++.h>
using namespace std;

int v, p;
int vs[3005], f[3005][3005];
int dis[3005][3005], pos[3005][3005];

int main(){
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d", &v, &p);
    for (int i = 1; i <= v; i++) scanf("%d", &vs[i]);
    sort(vs+1, vs+1+v);
    f[0][0] = 0;
    for (int l = 1; l <= v; l++){
        dis[l][l] = 0;
        for (int r = l+1; r <= v; r++) dis[l][r] = dis[l][r-1]+vs[r]-vs[(l+r)/2];
    }
    for (int i = 1; i <= p; i++) pos[v+1][i] = v;
    for (int j = 1; j <= p; j++){
        for (int i = v; i >= 1; i--){
            for (int k = pos[i][j-1]; k <= pos[i+1][j]; k++){
                if(f[i][j] > f[k][j-1]+dis[k+1][i])
                f[i][j] = f[k][j-1]+dis[k+1][i], pos[i][j] = k;
            }
        }
    }
    printf("%d", f[v][p]);
    return 0;
}

四边形不等式 学习笔记