n方DP：
f[i]=min{f[i],f[j]+(A[i]-B[j])*(A[i]-B[j])};
转化为一次函数形式：
f[j]+B[j]*B[j]=2*A[i]*B[j]+f[i]-A[i]*A[i];
所以就是以f[j]+B[j]*B[j]为y，2*A[i]为x的一次函数。
维护一个单调递增的下凸壳即可。
这个题我们注意到似乎有一个B[j]*B[j]在方程中，好像是个二次函数不能斜率优化。
实则不然，只要i和j的乘积项都是一次的，都可以用斜率优化。
至于到了高次，似乎要用四边形不等式。。。（还不会诶）
#include<bits/stdc++.h> #define RG register #define IL inline #define int long long #define DB double using namespace std; IL int gi() { RG int x=0,w=0; char ch=0; while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) w=1;ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=5e4+10; int H,T,q[N]; int n,L,c,sc[N],A[N],B[N],f[N]; IL DB Slope(int x,int y) { return 1.0*(f[x]+B[x]*B[x]-f[y]-B[y]*B[y])/(B[x]-B[y]); } signed main () { RG int i; n=gi(),L=gi(); for (i=1,B[0]=L+1;i<=n;++i) { c=gi(),sc[i]=sc[i-1]+c; A[i]=sc[i]+i,B[i]=sc[i]+i+L+1; } memset(f,0x3f,sizeof(f)); H=T=1,q[1]=0; for (i=1,f[0]=0;i<=n;++i) { //for (j=0;j<i;++j) // f[i]=min(f[i],f[j]+(A[i]-B[j])*(A[i]-B[j])); // f[j]+B[j]*B[j]=2*A[i]*B[j]+f[i]-A[i]*A[i]; while (H<T&&(DB)2*A[i]>=Slope(q[H+1],q[H])) ++H; f[i]=f[q[H]]+(A[i]-B[q[H]])*(A[i]-B[q[H]]); while (H<T&&Slope(i,q[T])<=Slope(q[T],q[T-1])) --T; q[++T]=i; } printf("%lld\n",f[n]); return 0; }
原文：https://www.cnblogs.com/Bhllx/p/10363105.html
