斜率优化

Vision271 · 2022-07-21 23:00:31 · 个人记录

概述

• 斜率优化可以加速转移式形如 dp_i=\max/\min(dp_j+a_i* a_j) 的 dp 的转移（这里所有的数组名称除了 dp 都是泛指）。

• 斜率优化的本质是将（对于 i 的）可行转移点 j<k，将 k 优于 j 的条件对应的式子化为 \dfrac{b_j-b_k}{a_j-a_k}\leqslant c_i 的形式（化形式，大小于号选取，etc. 都较随意，这里采取了我习惯的形式）。

• 可以看出，上式具有一种类似两点求连线斜率的形式，所以称为斜率优化。