[HNOI2008]玩具装箱TOY

Luogu P3195

bzoj 1010

思路

设$f_i$为前$i$个玩具的最小花费,则有转移方程

$$f_i=\min\limits_{0\leq j<i}\{f_j+(i-(j+1)+\sum \limits_{k=j+1}^iC_k-L)^2\}$$

令$L=L+1$,$S_i=\sum \limits_{j=1}^i C_j +i$,将原方程化简得

$$f_i=\min \limits_{0\leq j<i}\{f_j+S_i^2+S_j^2+L^2-2\cdot S_i\cdot S_j-2\cdot S_i\cdot L+2\cdot S_j\cdot L\}$$

则当对于$i$,$j_1$比$j_2$更优时有

$$2\cdot (S_i-L)<\frac{f_{j_2}-f_{j_1}+S_{j_2}^2-S_{j_1}^2}{S_{j_2}-S_{j_1}}$$

斜率优化即可

代码

#include <iostream>
#include <cstdio>

typedef long long LL;

int N, C[500010], q[500010];
LL L, sum[500010], S[500010], f[500010];

int main(){
    scanf("%d%lld", &N, &L);  L++;
    for(int i=1; i<=N; i++){
        scanf("%d", &C[i]);
        sum[i]=sum[i-1]+C[i];
        S[i]=sum[i]+i;	
    }
    int h=1, t=1;
    for(int i=1; i<=N; i++){
        while(2*(S[i]-L)*(S[q[h]]-S[q[h+1]])<=f[q[h]]-f[q[h+1]]+S[q[h]]*S[q[h]]-S[q[h+1]]*S[q[h+1]] && h<t) h++;
        f[i]=f[q[h]]+S[i]*S[i]+S[q[h]]*S[q[h]]+L*L-2*S[i]*S[q[h]]-2*S[i]*L+2*S[q[h]]*L;
        while((S[q[t-1]]-S[q[t]])*(f[q[t]]-f[i]+S[q[t]]*S[q[t]]-S[i]*S[i])<=(S[q[t]]-S[i])*(f[q[t-1]]-f[q[t]]+S[q[t-1]]*S[q[t-1]]-S[q[t]]*S[q[t]]) && h<t) t--;
        q[++t]=i;
    }
    printf("%lld\n", f[N]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注