不难得到递推式f[i]=min{f[j]+(sum[i]-sum[j])^2+m};
去掉min函数并展开：f[i]=f[j]+sum[i]^2-2*sum[i]*sum[j]+sum[j]^2+m
将含i的项与含j的项分离，并把单纯含j的项写在左边：f[j]+sum[j]^2=2*sum[i]*sum[j]+f[i]-sum[i]^2-m
现在把f[j]+sum[j]^2看做y，2*sum[i]看做k，sum[j]看做x，f[i]-sum[i]^2-m看做b。
对于每一个点(sum[j],f[j]+sum[j]^2)都是固定的，对于每一个i，斜率2*sum[i]也是固定的，而截距也就是b。
b越小，f[i]就越小。我们可以形象的理解为：一条斜率为2*sum[i]的线从下往上扫，扫到的第一个点就是答案。
我们构造一个队列，维护相邻两点间的斜率。如果能保证斜率单调递增，那么第一个满足斜率大于2*sum[i]的就是结果。
由于2*sum[i]也是单调递增的，所以不大于它的可以出队。时间复杂度N。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=500000+10;
int n,m,x,s[maxn],f[maxn],q[maxn];
int yval(int x,int y){
return f[y]-f[x]+s[y]*s[y]-s[x]*s[x];
}//计算y坐标的差
int xval(int x,int y){
return s[y]-s[x];
}//计算x坐标的差
signed main(){
while(cin>>n>>m){
for(int i=1;i<=n;i++){
scanf("%lld",&x);
s[i]=s[i-1]+x;
}
memset(f,0x3f,sizeof(f));
memset(q,0,sizeof(q));
int l=1,r=1;
q[l]=0,f[0]=0;
for(int i=1;i<=n;i++){
while(l<r&&yval(q[l],q[l+1])<=xval(q[l],q[l+1])*2*s[i])l++;
//当队首不满足斜率大于当前斜率，则出队
f[i]=f[q[l]]+(s[i]-s[q[l]])*(s[i]-s[q[l]])+m;
//计算f[i]
while(l<r&&yval(q[r-1],q[r])*xval(q[r],i)>=xval(q[r-1],q[r])*yval(q[r],i))r--;
//若队尾不满足单调性，则出队
q[++r]=i;
}
printf("%lld
",f[n]);
}
return 0;
}