四边形不等式优化 DP
2huk
·
·
算法·理论
定义
我们称 w 满足四边形不等式，当且仅当对于任意 a \le b \le c \le d 都有：
w(a,c)+w(b,d)\le w(a,d)+w(b,c)
即「交叉优于包含」。
:::info[定理 1]{open}
:::info[证明]
必要性是显然的。
移项可得 $w(a+1,b)-w(a,b)-w(a+1,b-1)+w(a,b-1) \le 0$，即 $w$ 的二维差分矩阵非负。所以二维差分矩阵上的子矩阵 $(b+1,d+1),(a,c)$ 的和为 $w(a,c)-w(a,d)-w(b,c)+w(b,d) \le 0$。
:::
四边形不等式可以用于 DP 的优化。具体的，对于转移式：
$$
f(i) = \min_{j<i} w(j,i)
$$
我们令 $\operatorname{opt}(i)$ 表示能够让 $f(i)$ 取到最小值的 $j$。即 $\operatorname{opt}(i)$ 满足：
$$
\begin{matrix}
f(i) = w(\operatorname{opt}(i), i) \le w(j,i) & \forall j < i
\end{matrix}
$$
显然 $\operatorname{opt}(i)$ 可能有多种取值。如果存在一种方法使得 $\operatorname{opt}(1) \le \operatorname{opt}(2) \le \dots \le \operatorname{opt}(n)$，则称 $w$ 满足决策单调性。
:::info[定理 2]{open}
若 $w$ 满足四边形不等式，则 $w$ 满足决策单调性。
:::info[证明]
考虑反证法。不妨设 $a \le b \le c \le d$，其中 $a = \operatorname{opt}(d),b=\operatorname{opt}(c)$。根据决策点定义有 $w(a,d) \le w(b,d),w(b,c)\le w(a,c)$，即 $w(a,d) - w(b,d) \le 0 \le w(a,c)-w(b,c)$。与四边形不等式矛盾。
:::
## 应用
有一类问题形如：将序列拆分成若干段，一个段 $[l,r]$ 的权值为 $w(l,r)$，求最小的权值和。有平凡的 DP：
$$
f(i) = \min_{j\le i}f(j-1)+w(j,i)
$$
:::info[定理 3]{open}
若 $w(j,i)$ 满足四边形不等式，则 $W(j,i)=w(j,i) + p_i+q_j$ 也满足四边形不等式。
:::info[证明]
将 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ 同加 $p_a+p_b+q_c+q_d$ 即可。
:::
即对于上述子段划分问题，若 $w$ 满足四边形不等式，则存在决策单调性。
一些题目会强制划分的段数为 $k$ 段。解决方法是 DP 多加一维。
一种常见的满足四边形不等式的 $w$ 是这样的形式：$w(l,r)=\sum_{l \le i \le j \le r}c_{i,j}$。
:::info[定理 4]{open}
若 $c_{i,j}\ge 0$，则 $w$ 满足四边形不等式。
:::info[证明]
考虑证明 $w(a,b-1)+w(a+1,b) \le w(a,b)+w(a+1,b-1)$。
考虑每个 $a \le i \le j \le b$ 的 $(i,j)$ 的贡献。发现 $i=a,j=b$ 对左式无贡献，对右式贡献 $c_{a,b}$，其余 $(i,j)$ 对两侧贡献相同。因为 $c_{a,b}\ge 0$ 所以 $w$ 满足四边形不等式。
:::
例如这些题目：
- [CF321E](https://www.luogu.com.cn/problem/CF321E)。
- [QOJ5507](https://qoj.ac/problem/5507)：这里 $c_{i,j}=[i<j \wedge a_i>a_j]$。
- [CF868F](https://www.luogu.com.cn/problem/CF868F)：这里 $c_{i,j}=[a_i=a_j]$。
当然四边形不等式优化 DP 不局限于这类题目。
## 实现
得知题目满足决策单调性后，考虑利用这个性质将朴素的 DP 优化。方法一般有两种：分治和二分队列。
### 分治
考虑实现函数 `solve(l, r, lt, rt)` 表示希望求解 $f(l) \dots f(r)$ 的值，并且已知决策点一定在 $lt \dots rt$ 中。
考虑求解暴力 $mid=\lfloor(l+r)/2\rfloor$。求出它的决策点 $\operatorname{opt}(mid)$ 后，递归求解 `solve(l, mid - 1, lt, opt[mid])` 和 `solve(mid + 1, r, opt[mid], rt)` 即可。
显然只会递归 $\log n$ 层，且每一层的 $[lt, rt]$ 总长为 $\mathcal O(n)$。复杂度为 $\mathcal O(n \log n)$。
注意这个做法需要保证 DP 顺序任意。而「无段数限制的子段划分问题」需要按从前往后的顺序 DP，即不能用分治解决。但是如果题目限制段数为 $k$，即第 $i$ 行从第 $i-1$ 行转移而来，就可以使用分治解决。
特别的，如果 $w$ 并没有快速的求解方法，但是如果已知 $w(i,j)$，可以快速得知 $w(i\pm 1,j)$ 或 $w(i,j\pm 1)$ 的值，在分治做法中可以用类似莫队的方法求解 $w$。可以证明其复杂度正确。
CF868F 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k, a[N], cl, cr;
int cnt[N], res;
int f[21][N];
void add(int x) { x = a[x]; res += cnt[x]; cnt[x] ++ ; }
void del(int x) { x = a[x]; cnt[x] -- ; res -= cnt[x]; }
int w(int l, int r) {
while (cl > l) add( -- cl);
while (cr < r) add( ++ cr);
while (cl < l) del(cl ++ );
while (cr > r) del(cr -- );
return res;
}
void solve(int l, int r, int lt, int rt, int k) {
if (l > r) return;
int mid = l + r >> 1;
int p = -1;
for (int i = lt; i <= min(mid - 1, rt); ++ i ) {
if (p == -1 || f[k][mid] > f[k - 1][i] + w(i + 1, mid)) {
p = i;
f[k][mid] = f[k - 1][i] + w(i + 1, mid);
}
}
solve(l, mid - 1, lt, p, k);
solve(mid + 1, r, p, rt, k);
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; ++ i ) cin >> a[i];
cl = 1, cr = 0;
for (int i = 1; i <= n; ++ i ) {
f[1][i] = w(1, i);
}
for (int i = 2; i <= k; ++ i ) {
solve(1, n, 0, n - 1, i);
}
cout << f[k][n];
return 0;
}
```
### 二分队列
二分队列做法解决了 DP 顺序固定的问题。
我们用三元组 $(j,lt_j,rt_j)$ 描述一个决策点 $j$，即所有 $f(lt_j)\dots f(rt_j)$ 的决策点都是 $j$。因为有决策单调性所以这样设计是合法的。
我们用一个队列维护目前所有可能作为将来决策点的 $j$，且满足单调性。考虑求解 $f(i)$ 时，首先把无用的队首修改或弹出。然后从队尾依次判断决策点 $i$ 是否更优。
具体的，对于当前的队尾 $(j, lt_j, rt_j)$，如果 $f(lt_j)$ 改用 $i$ 更优，则弹出这个队尾。循环这个过程。处理完后，对于当前的队尾 $(j, lt_j, rt_j)$，二分 $k$ 表示 $[lt_j,k]$ 仍然用 $j$ 转移，但是 $[k+1,rt_j]$ 改为用 $i$ 转移更优。
这样复杂度也是 $\mathcal O(n \log n)$。但是实现略复杂，而且不能用上面类似莫队的方法进行 $w$ 的求解。
P3515 代码（本题 $w(j,i)=h_j-h_i+\sqrt{i-j}$，数学推导容易证明其满足四边形不等式）：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int n, h[N];
double f[N];
double w(int j, int i) {
return h[j] - h[i] + sqrt(i - j);
}
int lt[N], rt[N];
deque<int> q;
void solve() {
q = deque<int>();
for (int i = 1; i <= n; ++ i ) {
while (q.size() && rt[q.front()] < i) q.pop_front();
if (q.size()) lt[q.front()] = i;
auto better = [&](int x, int y, int z) {
return w(x, z) > w(y, z);
};
while (q.size() && better(i, q.back(), lt[q.back()])) q.pop_back();
if (q.size()) {
int lo = lt[q.back()], hi = rt[q.back()], res = rt[q.back()] + 1;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (better(i, q.back(), mid)) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
if (lt[q.back()] <= res - 1) {
rt[q.back()] = res - 1;
} else {
assert(0);
q.pop_back();
}
if (res <= n) {
lt[i] = res, rt[i] = n;
q.push_back(i);
}
} else {
lt[i] = i, rt[i] = n;
q.push_back(i);
}
if (q.size()) f[i] = max(f[i], w(q.front(), i));
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; ++ i ) cin >> h[i];
solve();
reverse(h + 1, h + n + 1);
reverse(f + 1, f + n + 1);
solve();
reverse(f + 1, f + n + 1);
for (int i = 1; i <= n; ++ i ) cout << (int)ceil(f[i]) << '\n';
return 0;
}
```
## 优化区间 DP
一般的 $\mathcal O(n^3)$ 的区间 DP 是这样的：
$$
f(l,r)=\min_{k=l}^{r-1} f(l,k)+f(k+1,r)+w(l,r)
$$
比如经典的石子合并问题中，$w(l,r) = \sum_{i=l}^r a_i$。
我们定义，$w$ 满足区间包含单调性，当且仅当对于任意 $a \le b \le c \le d$，都有：
$$
w(b,c) \le w(a,d)
$$
:::info[定理 5]{open}
如果 $w$ 满足四边形不等式和区间包含单调性，则 $f$ 满足四边形不等式。
:::info[证明]
不会。
:::
类似的，定义 $\operatorname{opt}(l,r)$ 表示 $f(l,r)$ 的决策点。那么如果 $f$ 满足四边形不等式，当区间长度相同时也存在决策单调性。
:::info[定理 6]{open}
如果 $w,f$ 满足四边形不等式，那么 $\operatorname{opt}(l,r-1) \le \operatorname{opt}(l,r) \le \operatorname{opt}(l+1,r)$。
:::info[证明]
当 $l$ 固定时，定义 $F(k, r) = f(l,k)+f(k+1,r)+w(l,r)$。注意到 $F$ 的每一项都满足四边形不等式，所以 $F$ 满足四边形不等式。所以 $\operatorname{opt}(l,r-1) \le \operatorname{opt}(l,r)$。另一侧同理。
:::
那么枚举 $k$ 时，无需枚举 $[l, r-1]$，只需要 $[\operatorname{opt}(l,r-1),\operatorname{opt}(l+1,r)]$。注意到长度相同的 $f$ 做转移时总共花费 $\mathcal O(n)$。所以总复杂度 $\mathcal O(n^2)$。