题目大意：有N个数字a[N]，每输出连续的一串，它的费用是 “这行数字的平方加上一个常数M”。问如何输出使得总费用最小。（n<=500000）
分析：动态规划方程为：dp[i]=dp[j]+M+(sum[i]-sum[j])^2；
右边有一项为：sum[i]*sum[j]。考虑用单调队列。
令dp[i]=g，dp[j]+M+sum[i]^2+sum[j]^2=y,sum[j]=y,2*sum[i]=k
则上式变为g=y-kx，即y=kx+g。此为直线方程。
我们要使得g最小，即可以考虑有一条斜率为k的直线自下向上平移，设它接触到的第一个点为（xp,yp），则p为最佳决策点，所以最佳决策点的集合构成了一个下凸包的形状。又因为斜率k是2*sum[i]，随着i的递增，斜率k是递增的，所以凸包中的点具备单调性，可以使用单调队列来优化。
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 500005
int n,m,t,head,tail,arr[MAXN];
int f[MAXN],sum[MAXN];
int st[MAXN];
bool turnleft(int i,int j,int k)
{
int y1=f[i]+sum[i]*sum[i]-f[j]-sum[j]*sum[j];
int y2=f[j]+sum[j]*sum[j]-f[k]-sum[k]*sum[k];
int x1=(sum[i]-sum[j]);
int x2=(sum[j]-sum[k]);
if(x2*y1>x1*y2)return 1;
else return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=sum[i-1]+arr[i];
}
f[0]=0;//arr[1]*arr[1]+m;
head=tail=1;
st[tail++]=0;
for(int i=1;i<=n;i++)
{
int k;
for(;head<tail-1;)
{
if(f[st[head+1]]+sum[st[head+1]]*sum[st[head+1]]-f[st[head]]-sum[st[head]]*sum[st[head]]>2*sum[i]*(sum[st[head+1]]-sum[st[head]]))
break;
else head++;
}
k=st[head];
f[i]=f[k]+(sum[i]-sum[k])*(sum[i]-sum[k])+m;
while(head<tail-1&&(turnleft(i,st[tail-1],st[tail-2])==0))
{
tail--;
}
st[tail++]=i;
}
printf("%d
",f[n]);
memset(sum,0,sizeof sum);
memset(f,0,sizeof f);
memset(st,0,sizeof st);
}
return 0;
}