[bzoj1010][HNOI2008]玩具装箱

Description

有 $n$ 个物品,每个物品长度为 $c_i$ ,现在要把这 $n$ 个物品划分成若干组,每组中的物品编号是连续的,规定每组的长度 $x=j-i+sum_{k=i}^{j}c_k$ ,费用为 $(x-l)^2$ ,求最小费用.

Input

第一行输入两个整数 $n$ 和 $l$ ,接下来 $n$ 行输入 $c_i$ .

Output

一行表示最小费用.

Sample Input

5 4

Sample Output

HINT

$1;leq;n;leq;50000,1;leq;l,c_i;leq;10^7$

Solution

$f[i]$ 表示将前 $i$ 个物品分组所需最小费用.

$f[i]=min{f[j]+(i-j-1+sum[i]-sum[j]-l)^2}(j<i)$

$O(n^2)$ 会 $T$ ,考虑斜率优化.

当 $k>j$ 且 $f[i]_k<f[i]_j$ 时,

$f[i]_j=f[j]+(i-j-1+sum[i]-sum[j]-l)^2$

$f[i]_k=f[k]+(i-k-1+sum[i]-sum[k]-l)^2$

尽量将 $i,j$ 分离,设 $g(j)=j+sum[j],h(i)=i+sum[i]-1-l$ ,得

$f[i]_j=f[j]+(h(i)-g(j))^2$

$f[i]_k=f[k]+(h(i)-g(k))^2$

$f[i]_k<f[i]_j$ 的前提是

$f[k]-f[j]+(h(i)-g(k))^2-(h(i)-g(j))^2<0$

整理得 $frac{(f[k]+g(k)^2)-(f[j]+g(j)^2)}{g(k)-g(i)}<2; imes;h(i)$

设 $T(j_1,j_2)=frac{(f[j_2]+g(j_2)^2)-(f[j_1]+g(j_1)^2)}{g(j_2)-g(j_1)}$

则 $T(j_1,j_2)<T(j_2,j_3)<...$

(若存在 $T(j_{n-1},j_n)>T(j_n,j_{n+1})$ ,因为 $h(i)$ 单调递增,所以 $j_{n+1}$ 一定比 $j_n$ 优,即 $j_n$ 可以删去)

所以每次取元素时,将满足 $T(j_n,j_{n+1})<2; imes;h(i)$ 的 $j_n$ 出队(因为 $j_{n+1}$ 比 $j_n$ 优),然后取队首为 $j$ .

#include<set> 
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 50001
using namespace std;
typedef long long ll;
ll f[N],s[N],q[N],h,t,l,n;
inline ll sqr(ll k){
    return k*k;
}
inline ll x(ll k){
    return k+s[k];
}
inline ll y(ll k){
    return f[k]+sqr(x(k));
}
inline double cmp(ll p,ll q){
    return (double)(y(q)-y(p))/(double)(x(q)-x(p));
}
inline ll g(ll k){
    return k+s[k]-l;
}
inline void init(){
    scanf("%lld%lld",&n,&l);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    for(ll i=1,k;i<=n;i++){
        k=g(i)<<1;
        while(h<t&&cmp(q[h],q[h+1])<k) h++;
        f[i]=f[q[h]]+sqr(x(q[h])-g(i)+1);
        while(h<t&&cmp(q[t],i)<cmp(q[t-1],q[t]))
            t--;
        q[++t]=i;
    }
    printf("%lld
",f[n]);
}
int main(){
    freopen("toy.in","r",stdin);
    freopen("toy.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}