斜率优化入门
对于两个\(dp[i]\)的决策点\(j_1,j_2\)，满足当时\(\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\leq S_ij_2\)比\(j_1\)更优，则可以维护下凸壳来去除一些一定不优的决策点
可以证明，当\(\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\leq S_i\)时 \(j_2\) 比 \(j_1\) 更优，则上凸壳一定不优，维护下凸壳
反之，当\(\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\geq S_i\)时 \(j_2\) 比 \(j_1\) 更优则维护上凸壳
然后当\(S_i\)不具有单调性的时候可以二分出最优的斜率
当\(S_i\)具有单调性时有决策单调性，用单调队列维护答案
看某位大佬博客看到的总结：
-
写出 \(dp\) 方程后，要先判断能不能使用斜优，即是否存在 \(function(i)∗function(j)\)的项。
-
通过大小于符号或者 \(b\) 中 \(dp[i]\) 的符号结合题目要求 \((min/max)\) 判断是上凸包还是下凸包，否则死活求不出答案。
-
（单调性出锅 1 号）将方程变为\(\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\leq S_i\)或者 \(\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\geq S_i\) 或者 \(kx+b=y\)的形式，变化要遵循之前提到的原则，尤其是 \(X\) 表达式的单调性，结合图形会更好理解。如果 \(X\) 不单调，那么需要用到 CDQ 分治或者平衡树维护凸包。
-
（单调性出锅 2 号）注意是否具有决策单调性，有时候打表只能得到片面的情况。当斜率不是单调递增时该怎么办？由于我们不知道什么时候会在什么地方取得最优决策点，所以必须要保留整个凸包以确保决策有完整的选择空间，查找答案就只能二分了，而不能直接取队首，比如这道题 [任务安排 33 Loj10186 BZOJ2726就不满足，其证明放在后面。
-
（单调性出锅 3 号）当 \(X\) 非严格递增时，那么在求斜率时可能会出现 \(X(j_1)==X(j_2)\) 的情况，最好是写成这样的形式：return \(Y(j)⩾Y(i)?inf:−inf\)，而不要直接 return inf 或者 −inf，在某些题中情况较复杂，如果不小心画错了图，返回了一个错误的极值就完了，而且这种错误只用简单数据还很难查出来。
-
队列初始化要塞入一个点 \(P(0)\)，还是以 玩具装箱 toy[P3195] 为例，塞入 \(P(S[0],dp[0]+(S[0]+L)^2)\)即 \(P(0,0)\)，其代表的决策点为 \(0\)。
-
手写队列初始化是 \(h=1,t=0\) 由于塞了初始点导致 \(t\) 加 \(1\)
-
手写队列判断是否为空是 \({h⩽t}\)，而出入队判断时都需要有至少 \(2\) 两个元素才能进行操作。所以应是 \({h<t}\) 。
-
计算斜率可能会因为向下取整而出现误差，所以 \(slope\) 函数最好设为 \(long\) \(double\)
-
有可能会有一部分的 \(dp\) 初始值无法转移过来，需要手动提前弄一下，例如 摆渡车 [P5017]
-
在比较两个斜率时，尽量写上等于，即 \(“⩽”,“⩾”\) 而不是 \(“<”,“>”\)。这样写对于去重有奇效（有重点时会导致斜率分母出锅），但不要以为这样就可以完全去重，因为要考虑的情况非常复杂，所以还是应该加上 5 中提到的特判，万无一失。
-
判断斜率大小时尽量把除转换成乘，防止爆精度
BOSS题
这题插入的点不具有单调性，需要用平衡树维护，非常