四边形不等式优化dp学习笔记 [finished 1/2]

$四边形不等式学习笔记$

---

• $四边形不等式的定义$

摘自 $lyd's$ $book$

$定义一$

定义 $w(x, y)$ 为定义在整数域的二元函数, 若对于定义域上的任何整数 $a le b le c le d$, 满足 $w(a, c) + w(b, d) le w(b, c) + w(a, d)$, 则称函数 $w$ 满足 四边形不等式 .

$定义二$

定义 $w(x, y)$ 为定义在整数域的二元函数, 若对于定义域上的任何整数 $a < b$,
满足 $w(a+1, b+1) + w(a, b) le w(a+1, b) + w(a, b+1)$, 则称函数 $w$ 满足 四边形不等式 .

简记为 交叉小于包含 , 证明略 .

---

• $四边形不等式的应用$

$区间dp的优化 (石子合并)$

对于形如状态转移方程 $F[i, j] = min_{i le k < j}(F[i,k] + F[i, k+1]) + w(i, j)$, 可以使用 四边形不等式 进行优化.

$优化的前提有 3 个$,

1. $w 满足四边形不等式$ .

这是根本前提 .

2. $w有区间包含单调性$ : 对于任意 $a le b le c le d$, 满足 $w(b, c) le w(a, d)$ .

通过前提 $2$, 可以推导出 $F$ 也满足 四边形不等式, 证明略 .

3. 记 $p[i, j]$ 表示 $F[i, j]$ 的最优决策 $k$, 若前 $2$ 个前提都满足,
   则称 $p[i, j]$ 满足 二维决策单调性, 对于任意的 $i < j$, $p[i, j-1] le p[i, j] le p[i+1, j]$ .

关键. 证明略 .

---

$"石子合并"$ 这道题目满足上述的所有前提, 因此可以使用 四边形不等式 优化,
求解 $F[i,j]$ 时, 不再在 $[i, j)$ 中对 $k$ 进行暴力枚举, 而是在 $[p[i, j-1], p[i+1, j]]$ 中对 $k$ 进行枚举,

时间复杂度计算: $sum_{i=1}^Nsum_{j=i+1}^N p[i+1, j] - p[i, j-1] + 1 = sum_{i=1}^N N-i + p[i+1, N] - p[1, N-i] = N^2$ .

特别地, $p[i, i] = i, F[i, i] = 0$ .

注意环状处理 .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 5005;

int N;
int A[maxn];
int p[maxn][maxn];

ll sum[maxn];
ll F[maxn][maxn];

int main(){
        scanf("%d", &N);
        memset(F, 0x3f, sizeof F);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), A[i+N] = A[i];
        for(reg int i = 1; i <= N<<1; i ++) sum[i] = sum[i-1] + A[i], p[i][i] = i, F[i][i] = 0;
        for(reg int len = 2; len <= N; len ++)
                for(reg int i = 1; i+len-1 <= N<<1; i ++){
                        int j = i+len-1;
                        for(reg int k = p[i][j-1]; k <= p[i+1][j]; k ++){
                                ll t = F[i][k] + F[k+1][j] + sum[j] - sum[i-1];
                                if(t < F[i][j]) F[i][j] = t, p[i][j] = k;
                        }
                }
        ll Ans = F[0][0];
        for(reg int i = 1; i <= N; i ++) Ans = std::min(Ans, F[i][i+N-1]);
        printf("%lld
", Ans);
        return 0;
}

---

• $小例题$

IOI2000 邮局 .

---

$线性dp的优化 (待填坑)$