关于凸性的 things（wqs + slope trick + 闵可夫斯基和）

能够解决的问题

一些满足凸性的东西。

算法

wqs 二分

能解决的问题

让你求恰好用

k

步解决问题的最小代价，而且最小代价关于步数的函数有凸性。

如：求恰有

k

条白边的最小生成树，求把序列恰好分成

k

段的最小权值。

其实就是求一个凸函数

f(x)

的某一项。

思路

注：如有看不懂可以跟下文算法步骤一起食用。

下面假设上凸，如下图：

假如我们要求红点处的值。我们可以考虑：假设

f(x)

与一条直线相切，且我们知道那条直线的方程和切点，那是不是就能求了？（这里的条件看~~丝柯克~~似苛刻，其实不然，我们往下看）

那么我们需要：

直线斜率 $k$ ；
直线截距 $b$ ；
切点横坐标 $x$ 。

我们发现，由于

f(x)

凸，所以随着

k

减小，

x

增大（类比上图中

k1 > k2

），所以我们每次枚举，然后求切点横坐标，通过二分找到要求的点的切线对应的斜率

k

（上图中就是找到一个

k1 > k > k2

的

k

）。

然后我们有了

k

，如果刚好顺便求出了

b

那么不就求出了切点了吗？

算法过程

上述过程看似每一步都像拼凑的，可是我们写出算法过程：

二分出一个斜率 $k$ 。
根据我们的思路， $f(x) = kx + b$ ，那么 $b = f(x) - kx$ 。
由于直线是切线，则 $b$ 应最大（可以看图理解），所以我们求出最大的 $b$ 与其对应的 $x$ 即可。
于是求 $f(x)$ 的某处的值变成了求 $y = f(x) - kx$ 的最大值点。

与问题结合：

f(x)

是用

x

步解决问题的最下代价，那么

y = f(x) - kx

即为每用一步就付出

k

的代价情况下的最小代价（不限制步数）。这个东西一般都能非常快的求出来。

不可忽视的细节

考虑下图：

此时红点与相邻两点贡共线。我们发现此时你如果二分到斜率

k

，则你有可能求出的切点横坐标偏小，你就找不到切点横坐标为指定值对应的斜率。

我们的解决办法是：每次保证找到的切点永远最靠左，那么我们就可以二分出最大的切点横坐标不大于要求的点的横坐标的斜率（有点绕，建议看看图），那么问题迎刃而解。

例题

P2619 [国家集训队] Tree I - 洛谷

结合算法过程，那么我们只要二分

x

，然后求每选一条白边就给 MST 加

x

的权值的情况下的最小生成树（也就是白边权值

v \gets v + x

），直到此时恰好选了

k

条边，则此时就是答案。

注意细节，Kruskal 时同样边权的边黑边在先，这样就可以尽可能让白边数量少（切点横坐标小）。

slope trick

下面的讲解以下凸为例。

能够解决的问题

dp 的某一维满足凸性。

前置知识：凸函数的闵可夫斯基和

点集 $A$ 与 $B$ 的闵可夫斯基和为 $\{(x, y) | x = x_1 + x_2, y = y_1 + y_2, (x_1, y_1) \in A, (x_2, y_2) \in B\}$ 。

考虑下图（红、绿色凸函数的拐点集的闵可夫斯基和是黄色凸函数的拐点集）：

观察被标成相同序号的边：由于两个涂蓝的部分都是平行四边形，所以黄色凸函数的各部分斜率就是红、绿两色各部分斜率的归并（可以自己也多花几个图辅助理解）。

于是我们得到结论：两个凸函数的闵可夫斯基和的斜率是各自斜率的归并。

维护拐点的情况

思路

顾名思义，把 dp 有凸性的那一维通过“拐点”与正无穷大处的斜率维护。

拐点：右侧斜率比左侧大一（同一个地方可以有多个拐点），如下图（红点为拐点）：

例题

P4597 序列 sequence - 洛谷

设

dp_{i, j}

为考虑

1 \sim i

，使

a_i

变为

j

的最小代价。

通过天蒙与打表：

j

那一维有凸性。

考虑从

dp_{i - 1}

到

dp_i

：

转移式： $dp_{i, j} = \min_{k \leqslant j} dp_{i - 1, k} + |a_i - j|$ 。
后面的部分是定值，而前面的部分：

蓝色的部分的

j

对应的最优的

k

就是

j

本身；绿色的

j

对应的最优的

k

是函数的最小值。所以转移等价于：

绿色的部分直接变成黄色的部分：纵坐标是函数最小值的常函数。
整个函数加上 $y_2$ 。

于是最终变成灰色图像。

观察两步转移，我们发现函数最右侧的斜率永远为

1

（常函数+绝对值函数）。所以转移等价于：

删掉最大的拐点。
在 $a_i$ 处加两个拐点。
正无穷大处的斜率保持不变。

于是用一个堆维护拐点，就完了。

维护差分数组（斜率）的情况

思路

顾名思义，把 dp 有凸性的那一维通过差分数组与

x = 0

处的值维护。

例题

P9962 [THUPC 2024 初赛] 一棵树 - 洛谷

显然的 dp 是树形背包。

又一次通过天蒙与打表：

j

那一维有凸性。

设

dp_{u, j}

为

u

的子树内染了

k

个点的最小代价，观察转移：

\min_{son} (dp_{u, j} + dp_{son, k}) \to dp_{u, j + k}

，不就是

dp_u

与

dp_{son}

的闵可夫斯基和吗？

于是每次归并差分数组（用一个可并堆），做完了。

制作不易，点个赞呗~

关于凸性的 things（wqs + slope trick + 闵可夫斯基和）

文章操作

能够解决的问题

算法

wqs 二分

能解决的问题

思路

算法过程

不可忽视的细节

例题

slope trick

能够解决的问题

前置知识：凸函数的闵可夫斯基和

维护拐点的情况

思路

例题

维护差分数组（斜率）的情况

思路

例题

相关推荐

评论

关于凸性的 things（wqs + slope trick + 闵可夫斯基和）