slope

## slope trick ### 概述 在 $dp$ 过程中，可以维护凸函数的方法，要求 $dp$ 值呈凸函数且其斜率均为整数。 具体来说，是记录凸函数斜率的变化值，即在什么位置斜率$\plusmn 1$，例如凸函数 $f(x) = |x|$，它由一条斜率为 $-1$ 和 一条斜率为 $1$ 的 ......

# Slope Trick 学习笔记 ~~看算法名的时候还以为就是斜率优化~~ 一种维护 DP 的方法，需要满足 DP 式与斜率修改关系较大，比如：$$f_{i,j}=\min_{k<=j}(f_k)+|a_i-j|$$ 可以发现 $f_i$ 关于 $j$​ 的函数为凸函数，其斜率为正的部分显然没有 ......