BZOJ 1010 [HNOI2008]玩具装箱toy

题目大意

给你一堆物品，你可以制造多个容器容纳这些物品。每个容器可以容纳一段连续区间内所有的物品，建造一个容纳i~j物品的箱子的长度为$j-i+\sum{C_k}(i \le k \le j)$，制造费用为$(X-L)^2$，问最少的装下所有物品的制造价格。

我们列出朴素DP方程$f[i] = f[j]+(s[i] - s[j] - L)^2$

把他化简成斜率DP方程$F[j]+(s[j]+l)^2 = 2s[i](s[j]+L) + f[i]-s[i]^2$

具体证明见土地购买

套路&模板。

#include <cstdio>
#define x(i) s[i]
#define y(i) (f[i]+cuspow(s[i]+l))
long long cuspow(long long target)
{
	return target*target;
}
int n,a[50010],h,t,q[50010];
long long f[50010],s[50010],l;
int main()
{
	scanf("%d%lld",&n,&l);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	for(int i=1;i<=n;++i)
		s[i]=s[i-1]+a[i];
	for(int i=1;i<=n;++i) s[i]+=i;
	l++;
	for(int i=1;i<=n;++i)
	{
		while(h<t&&y(q[h+1])-y(q[h])<(s[i]<<1)*(x(q[h+1])-x(q[h]))) ++h;
		f[i]=f[q[h]]+cuspow(s[i]-s[q[h]]-l);
		while(h<t&&(y(i)-y(q[t]))*(x(q[t])-x(q[t-1]))<(x(i)-x(q[t]))*(y(q[t])-y(q[t-1]))) --t;
		q[++t]=i;
	}
	printf("%lld",f[n]);
	return 0;
}
//f[j]+(s[j]-L)^2 = 2*s[i] * (s[j]-L) + f[i]-s[i]^2
//f[i] = f[j]+(s[i] - s[j] - L)^2