斜率优化

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