「HNOI 2008」玩具装箱

发表于 | | 阅读次数:
字数统计: 429 字

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%