四边形不等式学习笔记

rlc202204 / 2024-08-28 / 原文

1.定义

1.1 四边形不等式

四边形不等式指的是二元函数 $w(l,r)$ 对于 $l_1 \le l_2 \le r_1 \le r_2$ 满足：

\[w(l_1, r_1) + w(l_2, r_2) \le w(l_2, r_1) + w(l_1, r_1) \]

也就是交叉优于包含。

四边形不等式的等价形式是：

\[w(l, r - 1) + w(l + 1, r) \le w(l, r) + w(l + 1, r - 1) \]

常见的满足四边形不等式的函数包括几类：

$w(l,r) = f(l) - g(r)$，显然不等号会去等。常见的有前缀和。
$w(l,r) = f(a_r - a_l)$，其中 $a_1 < a_2 < \dots < a_n$ 且 $f$ 是凸函数（也就是二阶差分非负）。比如 $f(x) = x^p(p > 1)$ 和 $f(x) = -x^p(0 < p < 1)$。
两个函数分别满足四边形不等式，则它们的和也满足。

1.2 单调性

如果函数 $w(l,r)$ 满足：

\[\forall l' \le l \le r \le r', w(l,r) \le w(l', r') \]

则其满足区间包含单调性。

对于一个动态规划来说，我们记录其最优决策点集合中最小的元素为 $opt$，下面记为最优决策点（注意一定要取最小的或者最大的）。

我们假设下面的函数计算都是 $O(1)$ 的，且都满足四边形不等式。

2. 离线版本

考虑转移方程：

\[f(i) = \min_{1 \le j < i}\{w(j,i)\} \]

直接暴力是 $O(n^2)$，我们考虑如何在 $O(n \log n)$ 内计算。

我们定义 $opt(i)$ 是 $f_i$ 的最优决策点。我们可以证明若 $i \le i'$，则 $opt(i) \le opt(i')$，也就是其具有决策单调性。

证明不难，oi-wiki 上有。

所以我们现在考虑分治计算：取中点 $m$，我们先算出 $f(m),opt(m)$，然后递归计算两边的值。考虑到两边的 $opt$ 集合被一分为二，所以每一层的总计算量都是 $O(n)$ 的，总共 $\log n$ 层，时间复杂度 $O(n \log n)$。

模板题 P3515 [POI2011] Lightning Conductor。

这道题转化一下就是 $w(l,r) = a_r- a_l - \sqrt{|r - l|}$。

这个函数的前半部分属于四边形不等式的函数类的第一种，后半部分属于第二种，所以这个函数满足四边形不等式。

然后我们就可以用分治求解了：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;

int n, h[N] = {0};

double w(int j, int i) {
	return h[j] - h[i] + sqrt(i - j);
}

void slv(int *f, int l, int r, int pl, int pr) {
	if (l > r)
		return;
	int mid = (l + r) / 2, p = pl;
	for (int i = pl + 1; i <= min(mid - 1, pr); i++)
		if (w(i, mid) > w(p, mid))
			p = i;
	f[mid] = max(f[mid], (int)ceil(w(p, mid)));
	slv(f, l, mid - 1, pl, p);
	slv(f, mid + 1, r, p, pr);
}
int f[N] = {0};
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &h[i]);
	slv(f, 1, n, 1, n);
	reverse(h + 1, h + n + 1);
	reverse(f + 1, f + n + 1);
	slv(f, 1, n, 1, n);
	for (int i = 1; i <= n; i++) 
		printf("%d\n", f[n - i + 1]);
	return 0;
}

3. 1D-1D 在线版本

求：

\[f(i) = \min_{1 \le j < i}\{f(j) + w(j,i)\} \]

考虑到 $f(j) + w(j,i)$ 显然也是满足四边形不等式的，所以决策单调性依然存在，但是由于我们依赖前面的结果，所以我们不能用分治来求解了。

这里我们用的方法是二分队列。

我们考虑决策点的值。

刚开始所有都是 0，然后我们加入 1 后一段后缀会变成 1，加入 2 后一段比之前后缀会变成 2，以此类推。

我们用队列存储 $(l,r,p)$ 表示当前 $[l,r]$ 的最优决策点都是 $p$，一开始只有 $(1,n,0)$，我们假设现在计算 $i$。

首先，我们计算 $f(i)$，显然其最优决策点就是现在的队首。

计算完之后，我们先判断队首是否为空，如果为空就弹出。

然后我们开始和队尾比较，每次看 $i$ 是否优于这一段的最优决策点，如果是，则弹出。最后我们有三种情况：

队列为空，则加入 $(i+1,n,i)$ 即可。
最后一段的 $r$ 的最优决策点是 $i$，这说明这一段的前半部分是 $p$，后半部分是 $i$，二分即可。
否则将剩下的后缀加入队列，最优决策点是 $i$。

时间复杂度 $O(n \log n)$。

模板题 P3195 [HNOI2008] 玩具装箱：

$w(l,r) = (s_r - s_l + r - l - 1 - L)^2$，显然满足四边形不等式。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 5e4 + 5;

struct Node {
	int l, r, p;
	Node (int _l = 0, int _r = 0, int _p = 0) :
		l(_l), r(_r), p(_p) {}
} q[N]; 
int fr, ba;

int n, L;
long long s[N] = {0};
long long f[N] = {0};

long long F(int j, int i) {
	return f[j] + (i - j + s[i] - s[j] - L - 1) * (i - j + s[i] - s[j] - L - 1);
}

int main() {
	cin >> n >> L;
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		s[i] = s[i - 1] + x;
	}
	fr = 1, ba = 0;
	q[++ba] = Node(1, n, 0);
	for (int i = 1; i <= n; i++) {
		f[i] = F(q[fr].p, i);
		if (++q[fr].l > q[fr].r)
			fr++;
		while (fr <= ba && F(i, q[ba].l) <= F(q[ba].p, q[ba].l))
			ba--;
		if (fr > ba)	
			q[++ba] = Node(i + 1, n, i);
		else if (F(i, q[ba].r) <= F(q[ba].p, q[ba].r)) {
			int l = q[ba].l - 1, r = q[ba].r;
			while (l + 1 < r) {
				int mid = (l + r) / 2;
				if (F(i, mid) <= F(q[ba].p, mid))
					r = mid;
				else
					l = mid;
			}
			q[ba].r = r - 1;
			q[++ba] = Node(r, n, i);
		}
		else if (q[ba].r != n)
			q[ba + 1] = Node(q[ba].r + 1, n, i), ba++;
	}
	cout << f[n] << endl;
	return 0;
}

4. 1D-2D 分组问题

4.1 内容

求：

\[f(i,j) = \min_{1 \le k \le i}\{f(k,j-1) + w(k,i)\} \]

也就是在上个问题的情况下，多了要求分多少组的限制。这里要求 $w$ 同时满足区间包含单调性。

第一种方法，我们按照 $j$ 从小到大处理，每层都是一个 1D-1D 问题，时间复杂度 $O(mn \log n)$

还有第二种方法。

不妨设 $opt(i,j)$ 是最优决策点，则我们可以证明：

\[opt(i,j-1) \le opt(i,j) \le opt(i+1,j) \]

所以我们考虑正序枚举 $i$，倒序枚举 $j$，由上面的式子得出 $opt(i - 1, j) \le opt(i,j) \le opt(i, j + 1)$，从而实现 $O(n^2)$ 的计算。

模板题 P4767 [IOI2000] 邮局加强版：

第二种方法：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 3005;
const int M = 305;

int n, m;
int a[N] = {0};

long long w[N][N] = {{0}};
long long f[N][M] = {{0}};
int p[N][M] = {{0}};

long long F(int i, int k, int j) {
	return f[k][j - 1] + w[k + 1][i];
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		int l = i, r = i, op = 0;
		long long val = 0ll;
		while (1 <= l && r <= n) {
			w[l][r] = val;
			if (op)
				l--, val += a[i] - a[l];
			else
				r++, val += a[r] - a[i];
			op = 1 - op;
		}
	}
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0ll;
	for (int i = 1; i <= n; i++) {
	    p[i][m + 1] = i - 1;
		for (int j = m; j >= 1; j--) {
		    p[i][j] = i - 1;
			for (int k = p[i - 1][j]; k <= p[i][j + 1]; k++) {
				if (f[i][j] > F(i, k, j))
					f[i][j] = F(i, k, j), p[i][j] = k;
			}
		}
	}
	cout << f[n][m] << endl;
	return 0;
}

4.2 应用

GYM103536A Guards

典型的分组问题，$w(l,r) = (r-l)(s_r - s_l)$，满足四边形不等式。

由于第二种方法不能滚动数组，所以我们只能用第一种方法分治计算，时间复杂度 $O(mn \log n)$。

提交记录

5. 2D-2D 区间合并

求：

\[f(l,r) = \min_{l \le k < r}\{f(l,k) + f(k + 1, r)\} + w(l,r) \]

要求 $w$ 还需满足区间包含单调性。

我们同样可以证明：

\[opt(i,j-1) \le opt(i,j) \le opt(i+1,j) \]

于是我们按照长度从小到大推，总时间复杂度 $O(n^2)$。

模板题石子合并的一排的版本，显然其满足四边形不等式和区间包含单调性，所以：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;

int n, a[N] = {0};

int opt[N][N] = {{0}};
int dp[N][N] = {{0}};

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], a[i] += a[i - 1];
	memset(dp, 0x3f, sizeof dp);
	for (int i = 1; i <= n; i++)
		dp[i][i] = 0;
	for (int i = 1; i <= n; i++)
		opt[i][i + 1] = i, dp[i][i + 1] = a[i + 1] - a[i - 1];
	for (int len = 3; len <= n; len++) {
		for (int i = 1; i + len - 1 <= n; i++) {
			int j = i + len - 1;
			for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++)
				if (dp[i][k] + dp[k + 1][j] + (a[j] - a[i - 1]) < dp[i][j])
					dp[i][j] = dp[i][k] + dp[k + 1][j] + (a[j] - a[i - 1]), opt[i][j] = k;
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}