dp 凸优化

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

凸函数介绍

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

---

WQS二分

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

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

模板题

2. CF739E Gosha is hunting

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

---

闵可夫斯基和

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

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

1. QOJ-5421 Factories Once More

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

2. GD 省集 tower

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

---

Slope Trick

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

1. CF713C

经典模板题。

2. ABC217H

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

3. [APIO2016] 烟火表演

又不会。

总结

===