qwqwq
Algha_Porthos
2020-07-31 18:46:02
$$f_i=f_j+(S_i-S_j)^2+M$$
令:$x<y<i$,$x$的决策优于$y$
$$f_x+(S_i-S_x)^2+M<f_y+(S_i-S_y)^2+M$$
$$f_x+(S_i-S_x)^2<f_y+(S_i-S_y)^2$$
$$f_x+S_i^2+S_x^2-2\times S_i\times S_x<f_y+S_i^2+S_y^2-2\times S_i\times S_y$$
$$f_x+S_x^2-2\times S_i\times S_x<f_y+S_y^2-2\times S_i\times S_y$$
$$f_x+S_x^2-(f_y+S_y^2) < 2\times S_i\times S_x-2\times S_i\times S_y$$
$$f_x+S_x^2-(f_y+S_y^2) < 2\times S_i\times (S_x-S_y)$$
$$2\times S_i\times (S_x-S_y)>f_x+S_x^2-(f_y+S_y^2)$$
$$S_i>\frac{f_x+S_x^2-(f_y+S_y^2)}{2\times (S_x-S_y)}$$
令$f_i+S_i^2=a_i$，$2\times S_i=b_i$
$$S_i>\frac{a_x-a_y}{b_x-b_y}$$
```cpp
const int N=525005,M=1055;
int n,k;
int aa[N],f[N],s[N],q[N];
int head=0,tail=0;
int a(int x,int y){
return f[y]+s[y]*s[y]-(f[x]+s[x]*s[x]);
}
int b(int x,int y){
return (s[y]-s[x]);
}
signed main(){
while(cin>>n>>k){
memset(f,0x3f,sizeof(f));
memset(s,0,sizeof(s));
f[0]=0;
head=0,tail=0;
for(int i=1;i<=n;++i)
scanf("%lld",&aa[i]),s[i]=s[i-1]+aa[i];
for(int i=1;i<=n;++i){
int kk=2*s[i];
while(head<tail&&a(q[head],q[head+1])<=kk*b(q[head],q[head+1]))
head++;
f[i]=f[q[head]]+(s[i]-s[q[head]])*(s[i]-s[q[head]])+k;
while(head<tail&&a(q[tail-1],q[tail])*b(q[tail],i)>=b(q[tail-1],q[tail])*a(q[tail],i))
tail--;
q[++tail]=i;
}
cout<<f[n]<<endl;
}
}
```