当前位置:首页 > 动态规划 > 单调DP > 正文
BZOJ1010[HNOI2008]玩具装箱toy
2388+

题目大意:将玩具装修,费用跟箱中玩具个数以及玩具总长度有关,已知计算公式即各个玩具长度,玩具装修必须编号连续,请问最小费用是多少?[洛谷P3195]

题目描述

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.1<=N<=50000,1<=L,Ci<=10^7

输出格式:

输出最小费用

输入输出样例

输入样例#1:

5 4
3
4
2
1
4

输出样例#1:

1

解题思路

斜率优化的DP,首先定义状态、写出状态转移方程:最终的结果是n个玩具的最小费用,那么f[i]就表示前i个玩具装箱的最小费用;转移就考虑最后一个容器(箱子)装的玩具是哪些,有前一箱转移过来。如果最后一项玩具装的是第j个到第i个,那么f[i] = f[j-1] + (X-L)^2。定义前缀和s[i]表示前i个玩具的长度之和,那么f[i] = f[j-1] + (i-j + s[i]-s[j-1] – L)^2。

公式化简:令p(x) = x + s[x] – L,q(x) = x + s[x-1],常量和变量区分开来,继续化简公式可得f[i] = f[j-1] + p(i)*p(i) + q(j)*q(j) – 2*p(i)*q(j)。此时,可以暴力枚举j=1到i,得到最后一箱的方案,转移得到f[i]的最小值。但是数据太大,会超时,我们可以考虑把需要用到的j放入队列中,不断去掉不可能最优的点。

不放设j1 < j2,如果j2更优,需要满足什么条件呢?把j1和j2代入,取j2时的f[i]需要小于取j1时的f[i],即他们相减,小于0。令g(x) = f[x-1] + q(x)*q(x),那么相减的结果就是g(j2)-g(j1) -2*p(i)*(q(j2)-q(j1)) < 0,已知的放在右边,因为j2>j1,q(j2)>q(j1),由g(j2)-g(j1) < 2*p(i)*(q(j2)-q(j1))可得(g(j2)-g(j1)) / (q(j2)-q(j1)) < 2*p(i)。

去掉不可能最优的j:这是一个斜率不等式,因为p(x) = x + s[x] – L单调递增,如果出现j1和j2两点斜率小于2*p(i),那么对于后面的i,斜率不等式同样满足,即j2永远比j1更优,即队列中的点,任意两点之间的斜率都要大于2*p(i),一旦发现小于的,删除j1(前面那个点),这样,队列中的点是少了,但还是需要遍历一遍寻找最优值。我们再细细考虑,对于3个点a、b和c,a比b优,b比c优,b可能比a和c都好吗?随着i增大,2*p(i)也增大,如果有这种可能,那么斜率ab小于2*p(i),斜率bc大于2*p(i),斜率是递增的。我们能否只维护一个斜率单调递增的序列,每次选最优的队头元素呢?可以的!因为一旦出现斜率递减,那么中间点b就不可能最优!

思考:j2更优的情况,如果p(i)单调递减会怎样?如果不等式是大于号又会怎样?

大于递增p,斜率全大于p,单调递减,最优在队尾;小于递增p,斜率全大于p,单调递增,最优在队头;大于递减p,斜率全小于p,单调递减,最优在队头;小于递减p,斜率全小于p,单调递增,最优在队尾。

程序实现

BZOJ1010[HNOI2008]玩具装箱toy:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!