斜率优化DP

终于学会了斜率优化DP，每次学一个新东西我都感觉要费老大劲。~~还是太菜了~~

学懂之后感觉其实并不是很难，当然能发明出这个算法的人不得不说真是太厉害了，能开创性地想到用函数维护DP方程，再根据当前斜率不变来二分（O(logn)）或单调队列（O(1)）查询出之前的最值进行转移。

而斜率优化的核心就已经说完了，具体讲就是：

将DP方程重构成一个一次函数的形式，然后使当前所求DP[i]被截距决定，而斜率用一个在当前 i 不会改变的值来表示，从而在斜率一定的时候去上下平移这条直线，找到在某个决策点 j 时，达到了最优的截距而得到最优的DP[i]。

那么函数的x就应该用跟 j 有关的式子（只跟 j 取值有关）表示，而 y 则就显然是被 j 决定的DP[j]。而 k 即是 x 前的系数，一定是由一个在当前 i 下不改变的式子。而有些不以 k 作系数的关于 j 的式子，可以和DP[j]放一起作为y。

而决策点 j 显然只有在一个上凸壳或者下凸壳上才可能成为最优的 j ,这个凸壳可以用一个单调队列维护。

（图是转luogu日报的，暂时未要到版权，若不允许转载请联系博主，侵删。）

第一个显然复杂度更优是O(n)的，而第二个则可以解决不满足斜率单调（例如横坐标不单调递增，例题P3299），不能出队head实时维护最优决策的问题。复杂度O(nlogn)。

每个DP[i]的斜率为正时，维护一个下凸壳，斜率依次要求单调不减，故：
1. 在每次加入新的点时，由于其横坐标更大，故此点一定要进去下凸壳中，而为了保证下凸壳依然下凸，需要保证当前点 i 与队尾 tail 的斜率大于 i 与(tail-1)的斜率，即为： K(i,tail)> K(i,tail-1) ，则 (while) (K(i,tail)<= K(i,tail-1))时，tail-- 将队尾出队，以此来维护下凸壳。
2. 当队列head和head+1的斜率小于等于当前 i 的斜率时，head这个点一定不是当前 i 对应直线向上平移时的第一个交点了，而且之后的直线斜率增大，故这个head再也不可能对答案有贡献，将其 while(K(head,head+1)<=slope(i)) \ \ head++，以此来维护单调队列保证head就是最优决策点。
每个DP[i]的斜率为负时，维护一个上凸壳，斜率要求单调不增，具体情况和上面类似，只是大于号小于号相反。

（待填.....）

（同上...）

（同上）

（同上.....）