BZOJ 1010 玩具装箱

题意

有n件玩具，玩具长度为ci。连续的玩具可以装进同一容器里，玩具之间要留有1个单位的空间。容器制作费为(X-L)^2，其中X表示容器长度，L表示常量。求最小费用。

数据范围

$$n\leq50000\ \ \ ;\ \ \ L,C_i\leq10^7$$

题解

动规方程

　　根据题目描述很容易列出动规方程：

　　其中 $$s[i]=\sum_{k=1}^{i} c[k]；$$

　　而X即为s[i]-s[j]+i-j-1；但这个X的表示实在太不好看。
　　我们发现i-j其实是可以跟s[i]-s[j]合到一起的，即令 c[i]=c[i]+1，则
　　所以X=s[i]-s[j]-1。
　　再将那个-1与L合并，即L=L+1，然后我们就得到整理后的方程：

斜率优化

证明决策单调性

　　要证明当j< k时，k决策比j要优，可以参考HZWER的证明，这里不再赘述。

斜率方程

　　已知k比j优，则
　　这里将s[i]-L当作一个整体来计算。
　　令
　　转移时将S[i]移到等式右边判断。

斜率优化的出队入队

• 出队
  　　队列要维护一个前后相邻点的斜率单调递增，因为斜率越小越有，所以要保证队首最优。如果G(q[st+1],q[st])/S(q[st+1],q[st])<=s[i]-L，就说明st+1比st优，st++。
• 入队
  　　如果G(q[en-1],q[en])/S(q[en-1],q[en])>(q[en],q[i])/S(q[en],q[i])，就en—。理由如图：

  代码

#include<cstdio>
long long f[50001],s[50001],l;
int q[50001];
long long Sqr(long long x) {return x*x;}
long long g(int x,int y) {return f[x]-f[y]+Sqr(s[x])-Sqr(s[y]);}
long long S(int x,int y) {return 2*(s[x]-s[y]);}
int main()
{
	int n,st=0,en=0;
	scanf("%d%lld",&n,&l);
	l++;
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&s[i]);
		s[i]+=s[i-1]+1;
	}
	for (int i=1;i<=n;i++)
	{
		while(st<en&&g(q[st+1],q[st])<=(s[i]-l)*S(q[st+1],q[st]))st++;
		f[i]=f[q[st]]+Sqr(s[i]-s[q[st]]-l);
		while (st<en&&g(q[en-1],q[en])*S(q[en],i)>g(q[en],i)*S(q[en-1],q[en])) en--;
		q[++en]=i;
	}
	printf ("%lld",f[n]);
	return 0;
}