分析
这里需要证明单调性,可以去看看我的另一篇题解
根据题意,可以很快发现暴力的状态转移方程
f[i]=f[j]+(s[i]-s[j]+i-j-1-len)*(s[i]-s[j]+i-j-1-len)
那它怎么会和斜率优化扯上关系呢?我们仔细看看,假设
A=s[i]+i,B=s[j]+j+len+1,那么原式变成
f[i]=f[j]+A*A-2*A*B+B*B
移项
f[j]+B*B=2*A*B+f[i]-A*A
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=5e4+10;
ll n,len;
ll a[N],b[N],f[N],q[N],s[N];
inline ll fir(int x)
{
return f[x]+b[x]*b[x];
}
inline long double check(int x,int y)
{
return (fir(x)-fir(y))/(b[x]-b[y]);
}
int main()
{
scanf("%lld%lld",&n,&len);
b[0]=len+1;
for (int i=1;i<=n;i++)
{
scanf("%lld",&s[i]);
s[i]+=s[i-1];
a[i]=s[i]+i,b[i]=a[i]+len+1;
}
int l=0,r=0;
for (int i=1;i<=n;i++)
{
while(l<r&&check(q[l+1],q[l])<=2*a[i]) l++;
int j=q[l];
f[i]=f[j]+(a[i]-b[j])*(a[i]-b[j]);
while(l<r&&check(q[r],q[r-1])>=check(i,q[r-1])) r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}