「HNOI 2008」玩具装箱

Description

题目链接:BZOJ 1010

P 教授要去看奥运,但是他舍不得他的玩具,于是他决定把所有的玩具运到北京。

他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维,再放到一种特殊的一维容器中。P 教授有编号为 $1\dots n$ 的 $n$ 件玩具,玩具经过压缩后会变成一维,第 $i$ 件件玩具压缩后长度为 $C_i$。

为了方便整理,P 教授要求:

  • 在一个一维容器中,玩具的编号是连续的;
  • 如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物。形式地说,如果要将 $i$ 号玩具到 $j$ 号玩具放到同一个容器中,则容器长度不小于 $x=j-i+\sum_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(x-L)^2$,其中 $L$ 是一个常量。

P 教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过 $L$。试求最小费用。

数据范围:$1\le n\le 5\times 10^4$,$1\le L,C_i\le 10^7$


Solution

这题可以说是斜率优化的入门题了吧(关于斜率优化的分析实现,请参见我的另一篇博客「算法笔记」斜率优化)。我们首先考虑朴素的动态规划,定义 $f_i$ 表示考虑到第 $i$ 个玩具的最小费用,记 $sum_i=\sum_{k=1}^i C_k$。转移方程为:

我们发现这里有一个平方项,所以可以考虑斜率优化。

为了表述方便,我们记 $x_i=sum_i+i$,$y_i=sum_i+i+1+L$,那么转移方程可以变形为:

我们任取 $j,k$ 满足 $0\le k<j<i$,当 $j$ 比 $k$ 要更好时,满足:

由于 $C_i>0$ 因此 $y_i$ 的值是递增的,可以直接除以 $y_j-y_k$ 得到:

很显然这已经是一个可以斜率优化的东西了,直接套斜率优化板子即可!

注意:此处 $x_0=0$,$y_0=1+L$,这两个值必须要初始化!

时间复杂度:$O(n)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>

const int N=5e4+5;
int n,L,c[N],q[N];
long long sum[N],x[N],y[N],f[N];

long long sqr(long long x) {
return x*x;
}
double slope(int i,int j) {
return 1.0*((f[i]+sqr(y[i]))-(f[j]+sqr(y[j])))/(y[i]-y[j]);
}
int main() {
scanf("%d%d",&n,&L);
x[0]=0,y[0]=1+L;
for(int i=1;i<=n;++i) {
scanf("%d",&c[i]);
sum[i]=sum[i-1]+c[i],x[i]=sum[i]+i,y[i]=sum[i]+i+1+L;
}
int l=1,r=0;
f[0]=q[++r]=0;
for(int i=1;i<=n;++i) {
while(l<r&&slope(q[l],q[l+1])<=2*x[i]) ++l;
f[i]=f[q[l]]+sqr(x[i]-y[q[l]]);
while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
0%