题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1010
题目大意：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。但他希望费用最小。
解题思路：我们可以很容易得到O（n^2）的状态转移方程：dp[i]=min{dp[j]+(sum[i]-sum[j]+i-j-1-l)^2}。显然这种写法会超时， 根据状态转移方程的性质，我们可以利用斜率优化，利用队列维护单调性，使得复杂度降为O（n）。
假设存在k<j<i,且j比k优，于是可以写出不等式dp[j]+(sum[i]-sum[j]+i-j-1-l)^2<=dp[k]+(sum[i]-sum[j]+i-j-1-l)^2
设s[j]=sum[j]+j，s[k]=sum[k]+k，C=l+1.
则原式可化为：dp[j]+(s[i]-s[j]-C)^2<=dp[k]+(s[i]-s[k]-C)^2
dp[j]+(s[j]+C)^2-2*s[i]*(s[j]+C)<=dp[k]+(s[k]+C)^2-2*s[i]*(s[k]+C)
(dp[j]+(s[j]+C)^2-dp[k]-(s[k]+C)^2)/(2*s[j]-2*s[k])<=s[i]
设yj=dp[j]+(s[j]+C)^2，yk=dp[k]+(s[k]+C)^2，xj=2*s[j]，xk=2*s[k]
令g(k,j)=yj-yk/xj-xk.
当①g(k,j)<=s[i],j比k优，k可抛弃。
②如果g(k,j)>=g(j,i)，那么j点便永远不可能成为最优解，可以直接将它踢出我们的最优解集。
1)若g(j,i)<=s[i]，那么就是说i点要比j点优，排除j点。
2)如果g(j,i)>s[i]，那么j点此时是比i点要更优，但是同时g(k,j)>=g(i,j)>s[i]。这说明还有k点会比j点更优，同样排除j点。
本质：维护一个斜率单调的队列。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=5e4+; LL l,C;
LL sum[N],dp[N],q[N]; //yj-yk/xj-xk
double Slope(int k,int j){
return double(dp[j]+(sum[j]+C)*(sum[j]+C)-dp[k]-(sum[k]+C)*(sum[k]+C))/(*sum[j]-*sum[k]);
} //dp[i]=min{dp[j]+(sum[i]-sum[j]+i-j-1-l)^2}
LL getDP(int i,int j){
return dp[j]+(sum[i]-sum[j]-C)*(sum[i]-sum[j]-C);
} int main(){
int n;
scanf("%d%lld",&n,&l);
C=l+;
for(int i=;i<=n;i++){
scanf("%lld",&sum[i]);
sum[i]+=sum[i-];
}
for(int i=;i<=n;i++){
sum[i]+=i;
}
dp[]=;
int head=,tail=;
q[tail++]=;
for(int i=;i<=n;i++){
while(head+<tail&&Slope(q[head],q[head+])<=sum[i]){
head++;
}
dp[i]=getDP(i,q[head]);
while(head+<tail&&Slope(q[tail-],i)<=Slope(q[tail-],q[tail-])){
tail--;
}
q[tail++]=i;
}
printf("%lld\n",dp[n]);
return ;
}