当前位置：首页 > news >正文

dp 凸优化

news 文章来源：https://blog.csdn.net/weixin_75161465/article/details/145310738 2025/5/20 1:23:42

时间有点仓促，过几天会补。
来自 czz 学长的课，SMWC -> Day4 。

凸函数介绍

凸函数即为一阶导单调的函数，在 OI 中通常体现为差分后单调的函数。这类具有凸性的问题在最优化问题中十分常见，通常具有其对应的线性规划或者费用流模型，也通常使用反悔贪心或者模拟费用流等方法解决。

WQS二分

详见 this 。
有一类问题，通常具有“选择恰好 $k$ 个”的标志，但是在 $d p$ 状态中记录 $k$ 复杂度又太高，此时通常使用 WQS二分 解决。
WQS二分 使用的前提为问题关于选择个数 $k$ 具有凸性。

1. P2619【国家集训队 2】Tree I

模板题

2. CF739E Gosha is hunting

凸性还可以联系到网络流，比如这题。
建立网络流模型，然后模拟网络流做法。 $O (n l o g n)$

闵可夫斯基和

$(min, +)$ 和 $(ma x, +)$ 卷积是常见的凸函数卷积，不难证明两个凸函数经过这样的卷积之后仍然是凸函数。（且这样的卷积常见于背包）
闵可夫斯基和常与分治等手段结合。

$(ma x, +)$ 卷积： $f(i) = max_{j+k=i} (g(j) + h(k))$ 。

1. QOJ-5421 Factories Once More

考虑 树形dp，设 $f_{u,i}$ 表示 $u$ 子树内选了 $i$ 个点的最大值。容易得到 $d p$ 转移方程， $max_{j+k=i} f_{u,j} + f_{v,k} + j \times k \times w(u, v)$
发现为凸函数，可以通过 $(ma x, +)$ 卷积做成闵可夫斯基和的形式，进行加速 $d p$ 。

2. GD 省集 tower

不会。
用闵可夫斯基和可以做到 $O (n l o g n)$ ，但是分类讨论的常数可达 $81$ 倍。

Slope Trick

Slope Trick 是一种优化 $d p$ 的方法。核心思想是储存 $d p$ 转移的关键信息（如分段函数的分界点）然后利用数据结构高效维护转移。
例如凸函数，我们只需维护初始的斜率，初始的值和斜率的变化点即可。
常见的维护操作有：函数相加，找最值，加一个一次函数，取前后缀max，平移，翻转等。

1. CF713C

经典模板题。

2. ABC217H

弄一个暴力 $d p$ ，设 $f_{i,j}$ 表示 $T_i$ 时刻角色在 $j$ 可能的最小伤害，转移就枚举上一次在哪：
$f i, j = minjk + l e n = j - l e n f i - 1, k + [(j > X i) = D i] \times ∣ j - X$
事件的贡献是一个下凸函数，发现转移是一个先平移后加一个下凸函数的形式，不难验证仍然 fi 仍然是一个下凸函数。考虑用两个堆分别维护拐点。由于是下凸函数，则最小值的左边是单调递减，最小
值的右边是单调递增。则只需把维护最小值左边的拐点位置统一减去 len，最小值右边的拐点位置统一加上 len 即可。加上的函数很明显拐点只有一个 Xi，插入拐点然后维护堆的大
小即可。

3. [APIO2016] 烟火表演

又不会。

总结

===

目录