https://loj.ac/problem/10188
题目描述
有(N)个玩具，每个玩具有一定的长度，在容器中玩具编号是连续的，装下第(i)到第(j)个玩具的容器长度为(j-i+sum_{k=i}^j c_k)，长度为(x)的容器代价为((x-L)^2)，求最小代价。
思路
我们令装下前(i)个玩具的长度为(sum[i]),可以直接列出状态转移方程(f[i]=min{f[j]+(sum[i]-sum[j]-L)^2})
化简后可得
[f[j]+sum[j]^2=2*sum[i]*sum[j]-sum[i]^2-L^2-sum[i]^2+2*sum[i]*L+f[i]
]
我们对这个等式维护下凸壳即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e4+10;
ll read()
{
ll res=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return res*w;
}
ll sum[N],s[N],q[N],f[N];
ll sqr(ll x)
{
return x*x;
}
int main()
{
ll n=read(),l=read();
for(ll i=1;i<=n;i++)
sum[i]=sum[i-1]+read(),s[i]=sum[i]+i;
ll head=0,tail=0;
for(ll i=1;i<=n;i++)
{
while(head<tail&&(f[q[head+1]]+sqr(s[q[head+1]])-f[q[head]]-sqr(s[q[head]]))
<=2*(s[i]-l)*(s[q[head+1]]-s[q[head]]))head++;
// cout<<i<<' '<<s[i]-s[q[head]]<<endl;
f[i]=f[q[head]]+sqr(s[i]-s[q[head]]-l-1);
while(head<tail&&(f[q[tail]]+sqr(s[q[tail]])-f[q[tail-1]]-sqr(s[q[tail-1]]))*(s[i]-s[q[tail]])
>=(f[i]+sqr(s[i])-f[q[tail]]-sqr(s[q[tail]]))*(s[q[tail]]-s[q[tail-1]]))tail--;
q[++tail]=i;
}
printf("%lld
",f[n]);
}