【学习记录】凸优化

KSCD_ · 2025-09-24 07:36:20 · 个人记录

之前看到 KingPowers 的专栏准备学来着，但一直鸽到现在，且目前只做了极少的例题，之后陆续更新。

大部分借鉴自 凸优化常见技巧 做题笔记 By KingPowers 和 从带权二分到闵可夫斯基和与凸生成函数 By 绝帆，拜谢拜谢拜谢。

带权二分（wqs 二分）

一般求解限制某个量恰为 x 的最值问题，设 f(x) 表示该问题的答案，首先要求 f(x) 关于 x 是上凸 / 下凸的。验证凸性可以使用感性理解、打表、费用流等方式。

由于 f(x) 是凸的，用斜率为 k 的直线去切该凸包时，切到的点随着 k 的变化是单调的。因此可以二分斜率 k 去切凸包，并求出切到的点，最终切到 (x,f(x)) 点即可求出答案。

为了避免细节讨论，在切到一条线时可以求其中 x 最小的点，二分出的也是能切到且不超过 x 的最大横坐标，答案同样是求出的截距 b 加上 x\times k。

在使用时若 f(x) 均为整数，只需要对整数斜率二分，这是因为此时所有的斜率均为整数。若 f(x) 是实数则需要使用实数二分。

P2619 [国家集训队] Tree I

题目链接，提交记录。

题意

给定 n 点 m 边的图，边有边权和黑白颜色，求其恰好包含 x 条白边的最小生成树。n\le 5\times 10^4,m\le 10^5。

题解

这题比较板，也是笔者第一道 wqs 二分题。

直接根据上述过程做，设 f(x) 表示 x 条白边的最小答案，感性理解其是下凸的。之后直接二分斜率 k，求出截距 f(x)-kx 的最小值及对应的最小 x，方式为将白边的边权减去 x，跑 Kruskal 时若边权相同则优先取黑边。

这样就做完了，复杂度 O(m\log m\log V)，当然也可以提前对两种边分别排序，check 时归并起来，复杂度 O(m\alpha(m)\log V)。凸性证明是困难的，略过不表。

HT-065-NOI T2 生成树

题目链接，题解。

本题 50 分的做法与上题相同，然而后半部分运用性质消掉了一层枚举，从而降低了复杂度。关键在于注意到多轮 wqs 二分本质相同，从而直接用一轮二分代替，下一题也有同样的优化思路。这是笔者第二道 wqs 二分题。

ARC168E Subsegments with Large Sums

题目链接，提交记录，提交记录'。

题意

给定长为 n 的正整数序列 a，要求将其分成 x 段，求总和不小于 s 的段数最大值。1\le x\le n\le 2.5\times 10^5,1\le a_i\le 10^9。

题解

首先显然有 O(n^3) 的暴力 DP，然后就发现答案关于 x 不是凸的，因此不能直接上 wqs 二分。先抛开这个不谈，发现本题的答案本身就具有单调性，可以直接先套一层二分答案 mid，转化为求需要 mid 段不小于 s 时，最多能划分成多少段。

设这个值为 f(mid)，感性理解 f(mid) 关于 mid 是上凸的，比如 mid=0 时可划分成 n 段，mid=1 时选择最短的合法区间合成一段，之后令合法段数增多需要减小的值不降。

因此可以使用 wqs 二分求出 f(mid)，对于斜率 k check 时需要最大化划分的收益，其中总和不小于 s 的段收益为 1-k，其余段收益为 1，要求在最大化收益的前提下最小化收益为 1-k 的段数。该过程可以 DP 解决，设 f_i 表示前 i 个数划分的最大收益和对应最小段数，则 f_i 可从 f_{i-1} 和 f_{p_i} 转移过来，其中 p_i 表示最大的 j 使得 [j+1,i] 的区间和不小于 s，复杂度为 O(n)。

这样有两层二分，总复杂度为 O(n\log^2n)，已经可以通过本题。然而还是很有优化空间的，因为凸包上也是一个前缀的 mid 合法。考虑对于整个凸包直接 wqs 二分，找到切到的最大合法点，之后向后扫过共线的所有点，找到最大的合法点即可。将其对 k 取最小值即为答案，时间复杂度 O(n\log n)。

题解区的绝大多数题解似乎是以 r-l 为区间代价再最小化，与上面的做法是本质相同的。

闵可夫斯基和

如上图，绿色凸包是红色和蓝色凸包做闵可夫斯基和的结果。

把边看作向量，可以发现原来两个凸包中每个向量均在新凸包中出现恰好一次。又由于凸包上的边按斜率单调排序，因此这样合并两个凸包的所有边即可，归并可以做到关于边数线性。

合并上 / 下凸包的操作是相同的，此时若有两个下凸包 f,g，它们的差分数组都是单增的，求其闵可夫斯基和时只需要将两个差分数组归并起来再前缀和回去即可。写出式子发现新凸包的 h_i=\min_{j+k=i}(f_j+g_k)，也就是用线性时间实现了两个凸包的 (\min,+) 卷积，这可以对 DP 等进行优化。

Gym103202L Forged in the Barrens

题目链接，提交记录。

题意

给定长为 n 的序列 a，要求将其划分为 k 部分，每部分的价值为其段内极差，对所有 k\in[1,n] 求最大价值和。n\le 2\times 10^5,1\le a_i\le 10^9。

题解

考虑暴力 DP，设 f_{i,j} 表示前 i 个数划分成 j 段的最大价值和，时间复杂度 O(n^3)。由于极差是最大值与最小值的差，然而取不到最值一定不优，因此直接扔掉最值限制，改为每部分任选两个数作差，得到的答案不变。这样可以设 f_{i,j,0/1,0/1} 表示第 i 个数划分到第 j 段，且是否已有减数 / 被减数的最大价值和，时间复杂度 O(n^2)。

然后优化不动了，但打表可以发现 f_{n,k} 关于 k 是凸的。凸的序列 DP 可以改成区间 DP 的形式，再用闵可夫斯基和优化合并，从而降低时间复杂度。对于本题，设 f_{l,r,0/1/2,0/1/2,i} 表示 [l,r] 区间内分成 i 段，且第一段和最后一段分别无贡献 / 有减数 / 有被减数的最大收益。转移时可任取 mid\in[l,r)，有转移式：

后三个式子直接把两边拿出来做 (\max,+) 卷积即可，用归并实现闵可夫斯基和可做到区间长度的复杂度。

由于只需要求 f_{1,n,0,0} 的所有值，每次直接取 mid=\lfloor\frac {l+r}2 \rfloor 即可，会形成一个分治结构，总长度是 O(n\log n) 的，因此总复杂度也是 O(n\log n) 的，然而在本题要乘上大概 3^3=27 的常数。

P11459 [USACO24DEC] It's Mooin' Time P

题目链接，提交记录。

题意

给出一个 01 串，单点修改 i 位置的字符需要花费 c_i 的代价，有且仅有首位为 1 且长为 L 的串为好串。对 [1,\lfloor\frac n L\rfloor] 内所有 k 分别求使原串有至少 k 个好串的最小代价。n\le 3\times 10^5,L\le 3,c_i\le 10^8。

题解

打表注意到答案关于 k 是下凸的，于是仍然套用上题做法分治，设 f_{l,r,x,y,k} 表示 [l,r] 区间包含了 k 个好串，且两边各有 x,y 个 0 的最小花费。这里 x,y\lt L 即可表示所有状态。转移时若 L=2 则 ly=0,rx=1 可多一个，若 L=3 则 ly=0,rx=2 或 ly=1,rx\ge1 可多一个，其余段数不变。

精细实现可以做到每次合并只做 L 次闵可夫斯基和。同时为了减小常数和避免细节，在区间长度低于 O(L) 时直接暴力枚举所有情况计入状态即可。总时间复杂度 O(2^L\frac nL+n\log nL^2)，后一项只有平方是因为每个区间的状态数为 \frac {len} L，可以约去一个 L。

slope trick

用于优化形如凸分段一次函数的 DP，这保证斜率单调，因此维护所有斜率变化的点，相同点的个数表示斜率变化量，这也要求斜率不能太大。

由于我还没怎么做所以概述之后再补。

P4597 序列 sequence

题目链接，提交记录。

题意

给定长为 n 的序列 a，每次操作可将某数增大或减小 1，求使其不降需要的最少操作次数。n\le 5\times 10^5,-10^9\le a_i\le 10^9。

题解

显然只会填原序列中有的数。因此可设 f_{i,j} 表示填完前 i 个数，第 i 个数填 j 的最小总次数。直接前缀优化转移即可做到 O(n^2)，因为数字种类数是 O(n) 的。

把 DP 式写出来，设 g_{i,j}=\min_{k=1}^j f_{i,k}，则 f_{i,j}=g_{i-1,j}+\left|j-a_i\right|。f_i,g_i 均是凸的分段一次函数，证明考虑初始的 f,g 均是凸的，而下凸包加绝对值一次函数和向前取最小值后均保持凸性。

因此维护函数的拐点，由于一直会向前取最小值，这说明斜率为正的部分不造成贡献，因此可只维护斜率为负的拐点，并认为最后一个点之后斜率是 0。之后依次加入每个 a_i，此时找出最后一个拐点 p 并分讨：

• 若 a_i\ge p，则 a_i 左边的部分斜率减小 1，右边斜率保持为 0，因此新加入一个拐点 a_i。
• 否则 a_i\lt p，此时 a_i 左边斜率减小 1，右边斜率增加 1，因此新加入两个拐点 a_i；p 之后的斜率变为 1，这会被取最小值操作推平，因此删掉一个 p；同时 p 处的值增大了 p-a_i 且仍为最小值，因此给答案加上 p-a_i。

整个过程容易用优先队列维护，答案为最终 p 处的取值，已经在过程中求出了，时间复杂度 O(n\log n)。