LNWC上其实讲过斜率优化，但是那阵子颓的不行，都没听懂。今天学习了一下DP的斜率优化。
斜率优化通常用来优化具有一下性质的DP问题：
- 将一段序列划分为多段连续区间
- DP方程中有形如$A_iB_j$的项。（例如$S_iS_j$）
设从状态$j$转移到状态$i$时$Dp_i = f(j)$，最佳方案取最小值（最大值同理），有$k \leq j \leq i$，若向状态$i$转移，$j$不比$k$差，则有$f(j) \leq f(k)$，移项，有形如$\frac{y_j - y_k}{x_j - x_k} \leq A_i$的不等式，这是$j$不比$k$差的必要条件。
我们再设$g(p, q) = \frac{y_p - y_q}{x_p - x_q}$，若$g(i, j) \leq g(j, k)$，我们可以直接丢掉状态$j$，原因如下：
若$g(i, j) \leq A_i$，则$i$不比$j$差。
若$g(i, j) > A_i$，可知$g(j, k) > A_i$，$k$也不比$j$差
由此可见，若$g(i, j) \leq g(j, k)$，状态$j$永远不会成为更优的状态，所以可以直接丢掉
需要证明的东西只有以上内容，下面简述一下流程。
首先我们搞一个双端队列来维护一个状态序列，这个序列当中，每三个位置元素$a, b, c$，都保证$g(c, b) > g(b, a)$。
将第一个状态的DP转移来源压入队列。
从$1 \ldots n$循环扫描（不一定从$1$开始），做如下四步：
- 当队列中队首往后的一个状态不比队首状态差时，弹出队首元素，直到队首状态比其后第一个状态更优为止。
- 用队首状态去更新当前状态。
- 考虑当前状态$i$，设队尾状态为$j$，队尾前一个状态为$k$，当$g(i, j) \leq g(j, k)$时，弹出队尾状态，直到$g(i, j) > g(j, k)$为止。
- 将当前状态压入队尾
个人感觉如果确定这道题可以用斜率优化DP，那么剩下的就是套路了，先推$g(p, q)$，然后按照流程来就可以了
代码如下
https://github.com/cjsoft/noip/tree/master/after_lnoi/d0518hdu2507.copy.cpp是自己徒手重写的hdu2829.cpp是自己推外加参考资料写出来的
