斜率优化DP
例题 任务安排
题面
\(n\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(N\) 个任务被分成若干批，每批包含相邻的若干任务。
从零时刻开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间为 \(T_i\)。在每批任务开始前，机器需要启动时间 \(S\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。
每个任务的费用是它的完成时刻乘以一个费用系数 \(C_i\)。请确定一个分组方案，使得总费用最小。
思路
- 裸DP
求出\(T,C\)前缀和\(sumT,sumC\),设\(F_{i,j}\)表示把前\(i\)个任务分成\(j\)批的最小费用
\(F_{i,j}=min\){\(F_{k,j-1}+(S*j+sumT_{i})*(sumC_{i}-sumC_{k})\)}
\(O(N^3)\)
- 费用提前计算
设\(F_{i}\) 示把前\(i\)个任务分成若干批的最小费用
\(F_{i}=min\){\(F_{j}+sumT_{i}*(sumC_{i}-sumC_{j})+S*(sumC_{N}-sumC_{j})\)}
\(O(N^2)\)
- 斜率优化DP
对解法二进行优化，先对状态转移方程进行变形
\(F_{i}=min\){\(F_{j}-(S + sumT_{i})*sumC_{j}\)}\(+sumT_{i}*sumC_{i}+S*sumC_{N}\)
把\(min\)函数去掉，把关于\(j\)的值\(F_{j}\)和\(sumC_{j}\)看作纵/横变量(由于\(j\)未知，\(F_{j},sumC_{j}\)会变化)，其余部分看作常数，得
\(F_{j}=(S+sumT_{i})*sumC_{j}+F_{i}-sumT_{i}*sumC_{i}-S*sumC_{i}\)
设\(k=S+sumT_{i},b=F_{i}-sumT_{i}*sumC_{i}-S*sumC_{i}\),则上述直线为一条以\(k\)为斜率，\(b\)为截距的直线.\(k\)已知，最小化\(F_{i}\),即为最小化截距\(b\).
所有待决策的点\((sumC_{j},F_{j})(j<i)\)可看作一个平面直角坐标系上的点集，观察可得有可能有贡献的点，一定形成一个下凸壳（相邻两点斜率递增）
实际上，对于一条斜率为\(k\)的直线，若某个顶点左边的线段斜率小于\(k\)，右边的线段斜率大于\(k\)，则它为决策点，如图
在本题中，每次会有一个新决策进入集合，横坐标递增，且\(S+sumT_{i}\)递增，所以，若我们只保留斜率大于\(S+sumT_{j}\)部分，则凸壳最左端最优
用单调队列维护凸壳，每次转移分3步：
- 检查队头，将斜率小于\(k\)的线段去掉
- 状态转移，算出\(F_{i}\)
- 将新决策从队尾插入，并维护凸壳
\(O(N)\)