斜率优化

2018-07-11 21:02:09


#include<bits/stdc++.h>
using namespace std;
int n,l;
double sum[50001],f[50001];
int head,tail;
int q[50001];
inline double a(int i){return sum[i]+i;}
inline double b(int i){return a(i)+l+1;}
inline double X(int i){return b(i);}
inline double Y(int i){return f[i]+b(i)*b(i);}
inline double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
int main(){
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++){
    scanf("%lf",&sum[i]);sum[i]+=sum[i-1];}
    head=tail=1;
    for(int i=1;i<=n;i++)
    {
        while(head<tail&&slope(q[head],q[head+1])<2*a(i))++head;
        f[i]=f[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head]));
        while(head<tail&&slope(i,q[tail-1])<slope(q[tail-1],q[tail]))--tail;
        q[++tail]=i;
    }
    printf("%lld\n",(long long)f[n]);
    return 0;
}