OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2008】玩具装箱

【题目描述】

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。但他希望费用最小。

【输入】

第一行输入两个整数N,L.接下来N行输入Ci。

【输出】

输出最小费用。

【输入样例】

5 4

3

4

2

1

4

【输出样例】

1

【数据范围】

1<=N<=50000,1<=L,Ci<=10^7

【题解】

嘛,先把状态转移方程写出来:f[i]=min(f[j]+(i-j-1+ΣCk-L)^2),k∈[j,i],f[i]表示前i件物品最小的费用。

先处理ΣCk,直接前缀和就好了,所以ΣCk=S[i]-S[j],其中S[i]表示前缀和。但是平方还是不好展开,所以再处理一下,把每个S[i]加上i,L也加上1,这样方程就变成了:f[i]=min(f[j]+(S[i]-S[j]-L)^2)

这个方程还是O(n^2)的,还是会TLE,所以考虑斜率优化,方程的最优性可以传递,所以化简以下不等式:

f[k]+(S[i]-S[k]-L)^2<=f[j]+(S[i]-S[j]-L)^2→(f[k]+(S[k]+L)^2)-(f[j]+(S[j]+L)^2)/2*(S[k]-S[j])<=S[i]

有了这个单调性方程,就可以用一个单调队列来维护了,每次维护队首元素,若斜率小于S[i],就将队首出队,然后用队首更新f[i]。将i加入队尾后维护队尾,直到队尾都满足斜率不等式。由于每个元素最多进队一次出队一次,所以复杂度是线性的。

PS.此题还有常数对数级算法,表示不会OTL

【代码】

线性的复杂度真真是极快的~

http://paste.ubuntu.com/7281603/

评论

© OI技术宅 | Powered by LOFTER