题意：给出一个数列C，一个数字M，将数列分成若干段，每段的代价为（设这段的数字为k个）：
dp[i]=min(dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+M)
若j1<j2且j2比j1优
dp[j1]+sum[i]^2+sum[j1]^2-2*sum[i]*sum[j1]+M>dp[j2]+sum[i]^2+sum[j2]^2-2*sum[i]*sum[j2]
dp[j1]-dp[j2]+sum[j1]^2-sum[j2]^2>2*sum[i]*(sum[j1]-sum[j2])
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int dp[],sum[],n,m,q[];
int getup(int j,int k){
return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];
}
int getdown(int x,int y){
return *(sum[x]-sum[y]);
}
int getdp(int i,int j){
return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);
}
int main(){
while (scanf("%d%d",&n,&m)==){
for (int i=;i<=n;i++){
scanf("%d",&sum[i]);
}
dp[]=sum[]=;
for (int i=;i<=n;i++)
sum[i]+=sum[i-];
int h=,t=;
q[t++]=;
for (int i=;i<=n;i++){
while (h+<t&&getup(q[h+],q[h])<=sum[i]*getdown(q[h+],q[h])) h++;
dp[i]=getdp(i,q[h]);
while (h+<t&&getup(i,q[t-])*getdown(q[t-],q[t-])<=getup(q[t-],q[t-])*getdown(i,q[t-])) t--;
q[t++]=i;
}
printf("%d\n",dp[n]);}
return ;
}