斜率优化DP(转移，出队的可行性证明)

斜率优化
斜率优化是针对一类 1D/1D 决策类动态规划问题，优化转移为 O(1)，能优化
成 1D/0D 问题，时间复杂度从 ?(?2) 优化成 ?(?)。我们结合一些实际的问题
来理解斜率优化。

用一道例题开头
[HNOI2008]玩具装箱
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他
使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容
器中。  P 教授有编号为 1⋯N的 N件玩具，第 i 件玩具经过压缩后变成一维长度为 Ci。为了方
便整理，P 教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器
中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第 i
件玩具到第 j个玩具放到一个容器中，那么容器的长度将为 ? = ? − ? + ∑??=? ?? 。  制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 x,其制作费为 (? − ?)2。其中 L是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容
器，甚至超过 L。但他希望费用最小。

下面是自己关于斜率优化DP的一些理解，主要是（转移，出队）的可行性证明
一：首先突破口就是在转态转移的时候是不是有许多重复的情况，如果有这种情况的话就可以考虑斜率优化。

二：主过程主要包含两步
1，遍历凹(凸)包，从首端维护最优最优点
代码形式：while(head+1<tail && getan(i,q[head+1])<=getan(i,q[head]))也可能是<=看具体情况。
这个原因很简单但同时也隐藏着一点性质就是第一条边的斜率一定是大(小)于f[i]的。

2，维护凹(凸)包，如果是求最小值就维护凹包，从末尾开始也分两种情况如图

这两步使所有边都是斜率上升的，这样每一次遍历就避免了重复的劣质点(f[i]是递增的)