[HNOI2008]玩具装箱
斜率优化入门题
显然有
\(f[i]=\min\{f[j]+(s[i]-s[j]+i-j-1-l)^2\}\)
拆开可得
\(f[j]+(s[j]+j)^2=f[i]+2(s[i]+i-1-l)(s[j]+j)\)
那么我们可以将决策看作是（\(s[j]+j\)，\(f[j]+(s[j]+j)^2\)）
由于\(2(s[i]+i-1-l)\)单调，直接单调队列即可。
需要注意的地方，实际中我们一般将斜率的除法，改成乘法，也就是移项，所以需要注意不等号的方向。所以推荐将大的那项写在前面。
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
typedef long long ll;
const int N=5e4+5;
ll f[N],s[N],a[N];
int q[N],h,t;
int n;
ll l;
ll X(int x){
return x+s[x];
}
ll Y(int x){
return f[x]+(x+s[x])*(x+s[x]);
}
ll up(int a,int b){
return Y(a)-Y(b);
}
ll down(int a,int b){
return X(a)-X(b);
}
ll sqr(ll x){
return x*x;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d %lld",&n,&l);
fo(i,1,n) {
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
h=t=1;
fo(i,1,n) {
while (h<t && up(q[h+1],q[h])<=2*(i+s[i]-1-l)*down(q[h+1],q[h]) ) h++;
f[i]=f[q[h]]+sqr(i+s[i]-1-l-q[h]-s[q[h]]);
while (h<t && up(i,q[t])*down(q[t],q[t-1])<= up(q[t],q[t-1])*down(i,q[t]) ) t--;
q[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}