斜率优化

斜率优化是一种用数据结构维护\(dp\)的某种单调性性质从而达到优化\(dp\)的效果。

抽象的说，斜率优化可通过维护一个上（下）凸壳优化形如\(f_i = min_{j=1}^{i-1}\{ f_j + g_{i,j}\}\)（\(max\)同理）的转移方程。

例题 [ZJOI2007] 仓库建设

设\(f_i\)为在第\(i\)个位置建造最后一个仓库的最小代价。

不难得出朴素的\(O(n^2)\)转移方程

换成前缀和的形式，令\(P_i=\sum_{j=1}^{i}p_i\), \(S_i=\sum_{j=1}^ix_i\times p_i\)

若决策\(j\)优于决策\(k\)，即

整理成斜率的形式

\(\because\)\(x_i\)单调递增，\(\therefore\)我们需要维护一个斜率单调递减的决策序列，即维护\(f_i\)函数的上凸壳。

使用单调队列维护即可，时间复杂度\(O(n)\)。

Code

例题 CF311B Cats Transport

设\(t_i\)为何时出发的人刚好接走它，\(s_i=\sum_{j=1}^it_i\)，\(f_{i,j}\)前\(i\)个人接走前\(j\)只猫的最小代价。

先忽略第一维考虑第二维转移，是和上面那题类似的模式。

使用同样的套路比较决策点，然后得到斜率的形式

同样使用单调队列维护，转移时多枚举一维即可，时间复杂度\(O(mp)\)

Code

习题

HNOI2008 玩具装箱 TOY

APIO2010 特别行动队

USACO08MAR Land Acquisition

未完待续。。。

斜率优化

原文：https://www.cnblogs.com/ACMSN/p/13223768.html