学习笔记——四边形不等式优化 DP

0. 前言

你打开了一道题，你发现是个 DP，你写出了转移方程

f_i = \min \limits_{0 \leq j < i} \{f_j + v_{j,i} \}

，你发现

v_{j,i}

可以

O(1)

计算。你兴致勃勃地写出了代码，却得到了满面 TLE。一看数据范围，

n \leq 2 \times 10^5

。

你点开题解，发现一种神奇的对于

v

的特殊性质进行优化的方法。这就是四边形不等式优化 DP。

1. 定义和性质

如果对于二维序列

w

中任意四个整数

a \leq b \leq c \leq d

都有

w_{a,d} + w_{b, c} \geq w_{a, c} + w_{b, d}

，则称

w

满足足四边形不等式关系。

性质

若对于任意两个整数

i < i + 1 \leq j < j + 1

，都有

w_{i, j + 1} + w_{i + 1, j} \geq w_{i, j} + w_{i + 1, j+1}

，那么

w

满足四边形不等式。

证明：

取

i + 1 < i + 2 \leq j < j + 1

，那么由上文的前提可得，我们令

i^{'} = i + 1

，则有

w_{{i^{'}},j+1} + w_{{i^{'}+1},j} \geq w_{{i^{'},j}} + w_{{i^{'}+1,j+1}}

，即

w_{i+1, j + 1} + w_{i + 2, j} \geq w_{i + 1, j} + w_{i + 2, j + 1}

。

两不等式相加，即

w_{i,j+1} + w_{i + 1, j} + w_{i+1,j+1} + w_{i+2, j} \geq w_{i,j}+w_{i+1,j+1}+w_{i+1,j}+w_{i+2,j+1}

，整理可得

w_{i, j+1} + w_{i + 2, j} \geq w_{i, j} + w_{i + 2, j + 1}

。

接着取

i+2<i+3 \leq j < j + 1

，可继续按照上面的做法推广，最终可得

w_{i, j + 1} + w_{i + 3, j} \geq w_{i, j} + w_{i + 3, j + 1}

。

可以发现我们可以取

i+3<i+4 \leq j < j + 1

等等，都可以证出类似的结论。即对于任意

a \leq b \leq c < c + 1

，都有

w_{a, c+1} + w_{b, c} \geq w_{a, c} + w_{b, c + 1}

。接着我们只需要把

c

按照类似的方法推广到

d

即可。

取

a \leq b \leq c + 1 < c + 2

，则有

w_{a, c+2} + w_{b, c+1} \geq w_{a, c+1} + w_{b, c + 2}

。

两不等式相加，即

w_{a, c+1} + w_{b, c} + w_{a, c+2} + w_{b, c+1} \geq w_{a, c} + w_{b, c + 1} + w_{a, c+1} + w_{b, c + 2}

，整理可得

w_{b, c} + w_{a, c+2} \geq w_{a, c} + w_{b, c + 2}

。

取

a \leq b \leq c + 2 < c + 3

，继续按照类似方法，有

w_{b, c} + w_{a, c + 3} \geq w_{a, c} + w_{b, c + 3}

。

可无限取

c

，即对于任意

a \leq b \leq c \leq d

，都有

w_{a, d} + w_{b, c} \geq w_{a, c} + w_{b, d}

。

至此，我们得以证明。

上述的结论通常用于证明

v

满足四边形不等式，与下文的 DP 优化关联不大。

PS：为什么叫四边形不等式？

https://cdn.luogu.com.cn/upload/image_hosting/5gskvj2a.png?x-oss-process=image/resize,m_lfit,h_1170,w_2225

对于任意四边形，显然有对角线的和

\geq

两对边之和，如图，

AD+BC \geq AC+BD

。证明方式为三角形两边之和大于第三边。

2. 优化 DP

考虑一类决策性 DP，其转移方程形如

f_i = \min \limits _{0 \leq j < i} \{f_j + v_{j, i}\}

。这类转移方程通常是类似这样的题目：

n

个数，要分成若干连续段，定义每一段的价值，要求最小化每段价值之和。这时我们设

f_i

表示前

i

个数分段的最小价值和，那么枚举

j

即枚举

i

属于哪一段，

v_{j,i}

则是这一段的价值。

首先要引入什么是决策，我们设

p_i

表示表示对于

i

而言，我们枚举的

0 \leq j < i

中，使得

f_j + v_{j,i}

取到最值（在上文的转移方程中即最小值）的

j

，则我们称

p_i

为

i

的决策点。

对于这一类问题，显然有朴素的

O(n^2)

计算方式。对于部分题目，如果

v

满足四边形不等式性质，我们可以考虑用下文的方式优化。

性质 1

若

v

满足四边形不等式，则

i

的决策点具有单调性。

性质 2

若有 $x < j$ 使得对于某个

i > j

，选取

j

的转移比

x

要优，则对于

i^\prime > i

，取

j

也比

x

优。容易发现

j

为

i

的决策点时与性质

1

等价，即性质

1

是性质

2

的特殊情况。

特别注意需要满足 $x<j$ 。

证明：

由于

j

比

x

对

i

的贡献更优，所以有：

f_j + v_{j, i} \leq f_x + v_{x, i}

。因为

v

满足四边形不等式关系，则有

v_{x, i^\prime} + v_{j, i} \geq v_{x, i} + v_{j, i^\prime}

，移项变为

v_{j, i^\prime} - v_{j, i} \leq v_{x, i^\prime} - v_{x, i}

。

将最后一个不等式和第一个不等式相加，有

f_j + v_{j, i^\prime} \leq f_x + v_{x, i^\prime}

。

证毕。

如何优化 DP

我们可以设初始时每个

i

的决策点都为

0

，然后从前往后，依次用决策点算出

f_i

并尝试用

i

作为新的决策点更改其他点。

由于性质

2

成立，所以如果

f_i

可以更新

f_x

，那么一定可以更新

f_{x+1}

到

f_n

。所以

f_i

能更新的点一定是末尾一段。假设能更新的是

p \sim n

，我们的目标就是找到

p

。容易发现是可以二分的。

我们考虑维护一个队列，每个点维护三个数

l,r,c

，表示

l \sim r

每个点的当前最优决策都为

c

。这个队列是对于

c

的单调队列。我们对于

i

，先从后往前找到

p

所在的

l,r,c

，然后在

[l,r]

中二分

p

的位置并更新队列即可。

当然也有一些其他实现方法，例如分治维护，复杂度也是

O(n \log n)

。

特别注意：

上文的做法对于四边形不等式是正确的，但对于普通的决策单调性是错误的。

对于普通的决策单调性 DP，只能保证最终的决策点是单调的，换句话说，只能保证性质

1

成立而不能保证性质

2

成立。

我们在维护单调队列进行更新的部分时，不能保证能找到

p

。

f_i

能更新的不一定是末尾一段。

我们可以通过几张图来更好地理解（下文的图中，横轴表示

j

，纵轴表示

f_j + v_{j,i}

）。

这张图给出的是

i=5

的一个例子。

假如我们只证明了决策单调性，那么对于

i=6

，图可能是这样：

容易发现决策点也是不递减的，但是对于

i=5

，

1

比

0

优，但是对于

i=6

，

0

却比

1

优。

这在证明

v

满足四边形不等时式后是不成立的，因为其不满足性质

2

。如果证明后，那么图可能是这样的：

容易看出，对于

j=0 \sim 4

的图，纵轴的点的相对关系是不变的。

所以可以看出，四边形不等式得到的结论强于决策单调性的。

注意，四边形不等式是证明 $p$ 单调性的一种充分不必要方式。即证明 $v$ 满足四边形不等式可以推出 $p$ 单调，但 $p$ 单调不一定要求 $v$ 满足四边形不等式。

例题

P3195 [HNOI2008]玩具装箱

考虑一个

O(n^2)

的 dp。

设

f_i

表示前

i

个玩具的最小总费用，

s_i

表示前

i

个玩具的长度和，即前缀和。

有转移方程：

f_i = \min \limits_{0 \leq j < i} \{f_j + (s_i-s_j+i-j-1-l)^2\}

。在这题中前文的

v

即后面的

(s_i-s_j+i-j-1-l)^2

，我们只需要证明

v

满足四边形不等式即可。

至于如何证明，通常可以考虑在本地

O(n^4)

枚举

a, b, c,d

，观察对于小数据是否满足，比较严谨的数学证明暂时略去。这里严谨的证明方式需要使用到文章开头的性质。

因为满足四边形不等式，把上述的优化 DP 方案加以修改即可。

代码：

CPP

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

#define int long long

const int N = 5e4 + 5;

int a[N], n, l, dp[N], sum[N], op[N];

struct Node
{
	int c, l, r;
}q[N];

inline int val(int i, int j) // 计算对于 j 而言，决策为 i 的答案
{
	int s = sum[j] - sum[i] + j - i - 1 - l;
	return dp[i] + s * s; // 即上文的 dp[i] + v
}

int hh, tt;

void insert(int x) // 用 x 更新决策方案
{
	int pos = n + 1; // 临界点
	while (hh <= tt && val(q[tt].c, q[tt].l) >= val(x, q[tt].l)) pos = q[tt--].l; // 找到用 x 作为决策点能更新到的队列，因为满足四边形不等式，所以更新的肯定是队列末尾的连续一段
	if (hh <= tt && val(q[tt].c, q[tt].r) >= val(x, q[tt].r)) // 如果我们找到了这个区间
	{
		int l = q[tt].l, r = q[tt].r;
		while (l + 1 < r) // 二分 l 到 r 中哪个点是临界点
		{
			int mid = l + r >> 1;
			if (val(x, mid) <= val(q[tt].c, mid)) r = mid;
			else l = mid;
		}
		q[tt].r = r - 1; // 更新队列和 pos
		pos = r;
	}
	if (pos != n + 1) q[++tt] = { x, pos, n }; // 如果可以更新，就在后面更新
}

signed main()
{
	scanf("%lld%lld", &n, &l);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	hh = tt = 0;
	q[0] = { 0, 1, n }; // 初始化，1 到 n 一开始的最优决策都是 0
	for (int i = 1; i <= n; i++)
	{
		dp[i] = val(q[hh].c, i); // 计算已经求出最优决策点对于现在点的 dp 值
		op[i] = q[hh].c; // 我们求出的 op[i] 表示每个点的最优决策
		if (q[hh].r == i) hh++; // 如果到达了队列的某一项末尾，则决策点改变，即 hh++
		q[hh].l = i + 1; // 重新计算 l
		insert(i); // 用 i 作为更新决策
	}
	printf("%lld\n", dp[n]);
	return 0;
}

由于四边形不等式优化 DP 的题目不多，而且大部分都较为类似，所以不增加更多例题了。

总结

在做一些决策性 DP 的问题时，如果

v

满足四边形不等式，我们可以考虑四边形不等式优化 DP，复杂度通常会由

O(n^2)

降至

O(n \log n)

。如何证明

v

满足四边形不等式？具体的数学证明我们通常不会在做题时证明，有时可以写

O(n^2)

的暴力，对于小数据验证四边形不等式，有时也可以感性理解。四边形不等式本身的性质有许多需要严谨证明的地方，建议自己再推一次。

除此之外，四边形不等式还可以优化决策型区间 DP，例如下面提到的再探石子合并。

例题：P8864 「KDOI-03」序列变换，AcWing 2889. 再探石子合并。

笔者水平有限，若有错误或建议欢迎提出，感谢。

学习笔记——四边形不等式优化 DP

文章操作

0. 前言

1. 定义和性质

性质

2. 优化 DP

性质 1

性质 2

如何优化 DP

例题

P3195 [HNOI2008]玩具装箱

总结

相关推荐

评论

学习笔记——四边形不等式优化 DP