题目大意：将玩具装修，费用跟箱中玩具个数以及玩具总长度有关，已知计算公式即各个玩具长度，玩具装修必须编号连续，请问最小费用是多少？[洛谷P3195]
题目描述
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.
输入输出格式
输入格式：
第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
输出格式：
输出最小费用
输入输出样例
输入样例#1：
5 4 3 4 2 1 4
输出样例#1：
1
解题思路
斜率优化的DP，首先定义状态、写出状态转移方程：最终的结果是n个玩具的最小费用，那么f[i]就表示前i个玩具装箱的最小费用；转移就考虑最后一个容器（箱子）装的玩具是哪些，有前一箱转移过来。如果最后一项玩具装的是第j个到第i个，那么f[i] = f[j-1] + (X-L)^2。定义前缀和s[i]表示前i个玩具的长度之和，那么f[i] = f[j-1] + (i-j + s[i]-s[j-1] – L)^2。
公式化简：令p(x) = x + s[x] – L，q(x) = x + s[x-1]，常量和变量区分开来，继续化简公式可得f[i] = f[j-1] + p(i)*p(i) + q(j)*q(j) – 2*p(i)*q(j)。此时，可以暴力枚举j=1到i，得到最后一箱的方案，转移得到f[i]的最小值。但是数据太大，会超时，我们可以考虑把需要用到的j放入队列中，不断去掉不可能最优的点。
不放设j1 < j2，如果j2更优，需要满足什么条件呢？把j1和j2代入，取j2时的f[i]需要小于取j1时的f[i]，即他们相减，小于0。令g(x) = f[x-1] + q(x)*q(x)，那么相减的结果就是g(j2)-g(j1) -2*p(i)*(q(j2)-q(j1)) < 0，已知的放在右边，因为j2>j1，q(j2)>q(j1)，由g(j2)-g(j1) < 2*p(i)*(q(j2)-q(j1))可得(g(j2)-g(j1)) / (q(j2)-q(j1)) < 2*p(i)。
去掉不可能最优的j：这是一个斜率不等式，因为p(x) = x + s[x] – L单调递增，如果出现j1和j2两点斜率小于2*p(i)，那么对于后面的i，斜率不等式同样满足，即j2永远比j1更优，即队列中的点，任意两点之间的斜率都要大于2*p(i)，一旦发现小于的，删除j1（前面那个点），这样，队列中的点是少了，但还是需要遍历一遍寻找最优值。我们再细细考虑，对于3个点a、b和c，a比b优，b比c优，b可能比a和c都好吗？随着i增大，2*p(i)也增大，如果有这种可能，那么斜率ab小于2*p(i)，斜率bc大于2*p(i)，斜率是递增的。我们能否只维护一个斜率单调递增的序列，每次选最优的队头元素呢？可以的！因为一旦出现斜率递减，那么中间点b就不可能最优！
思考：j2更优的情况，如果p(i)单调递减会怎样？如果不等式是大于号又会怎样？
大于递增p，斜率全大于p，单调递减，最优在队尾；小于递增p，斜率全大于p，单调递增，最优在队头；大于递减p，斜率全小于p，单调递减，最优在队头；小于递减p，斜率全小于p，单调递增，最优在队尾。
程序实现
