bzoj1010: [HNOI2008]玩具装箱toy—

方程

$\Large f(i)=min(f(j)+(s(i)-s(j)-1-L)^2)$

其中$s(i)$为i的前缀和再加上$i$

对于某个$i$若$j$比$k$优，则

$\large f(j)+(s(i)-s(j)-L-1)^2<f(k)+(s(i)-s(k)-L-1)^2$

展开可以化简成$\large (f(j)-f(k)+s(j)^2-s(k)^2)/(2*(s(j)-s(k)))<=s(i)-L-1$

这样我们就可以用斜率优化了

设点$i$的坐标为$（f(i)+s(i)^2,2*s(i)）$,维护一个下凸壳即可

代码

#include<cstdio>

#define maxn 50005

#define LL long long

int n,l,S,T,q[maxn];

LL f[maxn],s[maxn];

double calc(int a,int b){

    return (f[a]-f[b]+s[a]*s[a]-s[b]*s[b])/(2.0*(s[a]-s[b]));

}

void insert(int x){

    while(S<T-&&calc(x,q[T-])<=calc(q[T-],q[T-]))T--;

    q[T++]=x;

}

int main(){

    scanf("%d%d",&n,&l);l++;

    for(int i=;i<=n;i++){

        scanf("%d",s+i);

        s[i]+=s[i-]+;

    }

    T++;

    for(int i=;i<=n;i++){

        while(S<T-&&calc(q[S+],q[S])<=s[i]-l)S++;

        int x=q[S];

        f[i]=f[x]+(s[i]-s[x]-l)*(s[i]-s[x]-l);

        insert(i);

    }

    printf("%lld\n",f[n]);

    return ;

}

巴特西

bzoj1010: [HNOI2008]玩具装箱toy——斜率优化

方程

代码

最新文章

热门文章