[bzoj 1010][HNOI2008]玩具装箱toy

Description

  P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Input

  第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

  输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

Solution

f(i)表示把前i个玩具放起来的最小花费

容易推出

f\left[i\right]=min\begin{Bmatrix}f[j]+(i-(j+1)+sum_{i}-sum_{j}-L)^{2}\end{Bmatrix}

时间复杂度O(n^{2})

考虑斜率优化

假设k<j<i,当前的阶段为i,决策为j,kj决策比k更优

那么由已知可以推出

f[j]+(i-(j+1)+sum_{i}-sum_{j}-L)^{2}<f[k]+(i-(k+1)+sum_{i}-sum_{k}-L)^{2}

这式子是不是看起来很烦,我们简化下

G(i)=sum_{i}+i\alpha =1+L,则原式可化为

f[j]+(G[i]-(G[j]+\alpha))^{2}<f[k]+(G[i]-(G[k]+\alpha))^{2}

一般斜率优化都要凑成形如

\frac{y_{j}-y_{k}}{x_{j}-x_{k}}=F_{i}

那么我们把原式展开,得

f[j]+G[i]^{2}+(G[j]+\alpha)^{2}-2G[i](G[j]+\alpha)<f[k]+G[i]^{2}+(G[k]+\alpha)^{2}-2G[i](G[k]+\alpha)

整理下(公式恐惧症的不要走啊喂。。),得

f[j]-f[k]+(G[j]+\alpha)^{2}-(G[k]+\alpha)^{2}<2G[i](G[j]+\alpha)-2G[i](G[k]+\alpha)

看见曙光了23333,进一步整理,移项,得

f[j]-f[k]+(G[j]+\alpha)^{2}-(G[k]+\alpha)^{2}<2G[i](G[j]-G[k])

显然下一步就是把右边的G[j]-G[k]除过去,但是值得注意的是,这是不等式

那么是否需要变号呢?答案是否定的

已知k<j<isum数组严格递增(由玩具的大小都大于0可以推出)

求证:G[j]>G[k]

证明:原式可化为sum[j]+j,sum[k]+k

考虑作差法,G[j]-G[k]\Leftrightarrow sum[j]+j-sum[k]-k

sum[j]-sum[k]>0,j-k>0,故G[j]-G[k]>0,即G[j]>G[k])

证毕。

最终的式子是:

\frac{f[j]-f[k]+(G[j]+\alpha)^{2}-(G[k]+\alpha)^{2}}{2(G[j]-G[k])}<G[i]

那么我们可以得出的结论是,决策jk优当且仅当

\frac{f[j]-f[k]+(G[j]+\alpha)^{2}-(G[k]+\alpha)^{2}}{2(G[j]-G[k])}<G[i]

Y(x,y)=f[x]+(G[x]+\alpha)^{2}-f[y]-(G[y]+\alpha)^{2}X(x,y)=2(G[x]-G[y])

那么斜率的计算公式为k(x,y)=\frac{Y(x,y)}{X(x,y)}

我们知道,如果k(i,j)>G[i],那么ji劣,所以j点就被kill了

反之,k(i,j)<=G[i],说明ij劣,即斜率保持向下凸,为了维护好这个下凸壳,下一个决策点如果是e且满足k(i,j)<k(j,e),那么说明i可以直接连接e,即j被kill了

综上所述,我们可以得出单调队列的维护方式:

初始时,考虑删除比当期决策辣鸡的点,即不断地取队头head,次队头rhead,如果满足k(rhead,head)\leq G[i](注意符号的变化,因为要尽可能的最小化规模,所以小于等于),那么就可以删去队头(由刚才推导的较优决策条件可以得知)

然后利用队头更新dp

考虑维护队尾,假设队尾是a,b,c,将要进队的是d,且满足k(d,c)\leq k(c,b),那么这就不满足下凸性质了,需要删除c

由于每个元素只会入队1次,所以时间复杂度为O(n)

 

发表评论