Slope Trick 学习笔记

看算法名的时候还以为就是斜率优化

一种维护 DP 的方法，需要满足 DP 式与斜率修改关系较大，比如：$$f_{i,j}=\min_{k<=j}(f_k)+|a_i-j|$$

可以发现 \(f_i\) 关于 \(j\)​ 的函数为凸函数，其斜率为正的部分显然没有必要保留

令 \(g_i=|a_i-j|\)，\(g_i\) 关于 \(j\) 可以视为一个 \(V\) 型的函数，问题转化为如何快速将两者相加

只考虑函数间的大小关系来说，\(g_i\) 相当于对 \(j \in(-\infty,a_i]\) 斜率 \(-1\) ，对 \(j \in (0,+\infty)\) 斜率 \(+1\)

那么维护方法就有了：

维护 \(w\) 为最低点的权值，在斜率变化的位置加入一个数表示斜率 \(+1\) ，分每次加入的 \(g_i\) 中 \(a_i\) 与当前最低点的位置关系即可

例题：

CF713C Sonya and Problem Wihtout a Legend

纯模板

P3642[APIO2016]烟火表演

讨论一下发现转移就是分类改变斜率，于是可以套用上述方法

然而此题需要维护斜率大于等于 \(0\) 的部分，所以动态维护最小值不太方便，但最大值很容易得到，于是在维护完斜率后倒推最小值即可