【bzoj1010】[HNOI2008]玩具装箱toy

2014年11月28日4,2407

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

题解

2014.3.20

dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2) (j<i)

令f[i]=sum[i]+i,c=1+l

则dp[i]=min(dp[j]+(f[i]-f[j]-c)^2)

1.证明决策单调性

假设在状态i处的k决策优与j决策,即

dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2

则对于i后的所有状态t,要证明决策单调性

即dp[k]+(f[t]-f[k]-c)^2<=dp[j]+(f[t]-f[j]-c)^2

只要证

dp[k]+(f[i]+v-f[k]-c)^2<=dp[j]+(f[i]+v-f[j]-c)^2

只要证

dp[k]+(f[i]-f[k]-c)^2+2*v*(f[i]-f[k]-c)+v^2<=dp[j]+(f[i]-f[j]-c)^2+2*v*(f[i]-f[j]-c)+v^2

只要证

2*v*(f[i]-f[k]-c)<=2*v*(f[i]-f[j]-c)

即f[k]>=f[j](显然)

证明完毕

2.求斜率方程

因为dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2

展开

dp[k]+f[i]^2-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]+f[i]^2-2*f[i]*(f[j]+c)+(f[j]+c)^2

dp[k]-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]-2*f[i]*(f[j]+c)+(f[j]+c)^2

即(dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i]

f[i]是单调递增的,我们使用队列维护一个下凸壳,每次取出队头作为决策

加入决策i时,令队尾为q[r],前一个为q[r-1]

满足斜率(q[r],i)<斜率(q[r-1],q[r])时,显然队尾是无效的,将其弹出

2015.7.14 UPD:更新了能看的代码

2014.11.28

决策单调性这个看论文吧

http://wenku.baidu.com/link?url=UQoesURrEsUM4NvE5ZacHn8kAk5HgZTj5uMfmZEgJFQs6UVEHQ2s8zH7IiTT7DIn47SfxzTVY041L5tzDVltl1WSUa35uMiwFp8gQNpnUES

 

  1. 怎么看着证明第一行有点不对吗。。
    黄学长您确定是dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-dp[j]-c)^2
    而不是 dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2 ?
    我是蒟蒻错了请轻喷= =
    不过不管是对错还是上下文好像都不对啊。。。