qwqwq

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}$$


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;
    }
}