题目链接

[HNOI2008]玩具装箱

题目描述

P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。
P教授有编号为$1 \cdots n$的$n$件玩具,第$i$件玩具经过压缩后的一维长度为$C_i$。
为了方便整理,P教授要求:

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

制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为$x$,其制作费用为$(x-L)^2$。其中$L$是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过$L$。但他希望所有容器的总费用最小。

输入格式

第一行有两个整数,用一个空格隔开,分别代表$n$和$L$。
第$2$到第$(n+1)$行,每行一个整数,第$(i+1)$行的整数代表第$i$件玩具的长度$C_i$。

输出格式

输出一行一个整数,代表所有容器的总费用最小是多少。

样例输入

5 4
3
4
2
1
4

样例输出

1

说明/提示

对于全部的测试点$1 \leq n \leq 5 \times 10^4$,$1 \leq L \leq 10^7$,$1 \leq C_i \leq 10^7$。

题解

题意:有$n$个物品,每个物品都有长度$C_i$,要求吧每个物品装进任意个箱子里使花费最小,给定$L$。
花费计算公式如下:
$x=j-i+\sum\limits_{k=i}^{j}C_k$
$ans=(x-L)^2$
看到这里我们首先就想到dp。
转移方程为:
以下$i$均表示$i$到$j$装一个箱子
$dp[j]=min(dp[i-1]+(x(j,i)-l)^2)$
$i \le j$
$x(j,i)=s[j]-s[i-1]+j-i$
$s[i]$表示$\sum\limits_{k=1}^{i}C_k$
那么这样计算的话时间复杂度就是$O(n^2)$的,显然过不了此题。
那么我们考虑到用斜率优化。
我们假设有$k,i$,满足$k \lt i \le j$,且$i$的决策笔$k$的决策优,
那么$k,i$肯定满足:
$dp[i-1]+(s[j]+j-l-(s[i-1]+i))^2<dp[k-1]+(s[k]+k-l-(s[k-1]+k))^2$
我们化简一下上面的式子:
我们令:
$a=s[j]+j-l$
$b[i]=s[i-1]+i$
那么原式化简后就是:
$\frac{(dp[i-1]+b[i]^2)-(dp[k-1]+b[k]^2)}{(b[i]-b[k])}<2a$
因为对于每个确定的$j$来说$a$是常数,所以就可以用斜率优化来优化我们的dp了。
用凸包来保证dp的时间复杂度,具体实现看代码。
上代码:
注:代码中i表示i到j装一个箱子,k同上。

#include<bits/stdc++.h>
using namespace std;
int n,L;
int c[50009];
long long dp[50009],s[500009];
int pp[50009],l,r;
long long js(int i,int k){return 1.0*((dp[i-1]+(s[i-1]+i)*(s[i-1]+i))-(dp[k-1]+(s[k-1]+k)*(s[k-1]+k)))/(s[i-1]+i-s[k-1]-k);}
int main(){
    scanf("%d%d",&n,&L);
    for(int j=1;j<=n;j++){
        scanf("%d",&c[j]);
        s[j]=s[j-1]+c[j];
    }
    pp[0]=1;
    for(int j=1;j<=n;j++){
        while(l<r && js(pp[l+1],pp[l])<2*(s[j]+j-L)) l++;
        dp[j]=dp[pp[l]-1]+(s[j]-s[pp[l]-1]+j-pp[l]-L)*(s[j]-s[pp[l]-1]+j-pp[l]-L);
        while(l<r && js(pp[r],pp[r-1])>js(j+1,pp[r])) r--;
        pp[++r]=j+1;
    }
    printf("%lld",dp[n]);
    return 0;
}