BZOJ 1096 [ZJOI2007]仓库建设

题目大意

给你一个直线，直线上有一些点，每个点有着p[i]个东西，我们要在几个点设立仓库存储这些东西，每件东西挪动1单位长度需要1元，在每个点搭建仓库需要c[i]元，问所有东西都挪到仓库里需要的最小花费。

这道题难点就是求出每两个点之间进行运输所需要花费的价钱，我们令s[i]表示1~i所有东西送到i需要的价钱，sb[i]表示1~i一共有多少东西，我们得到transport(i,j)（从i运输到j的花费）就等于$s[j]-s[i]-sb[i]*route(i,j)$（i到j路程）。

之后我们就可以得到朴素DP方程$f[i]=f[j]+c[i]+s[i]-s[j]-sb[j]*(x[i]-x[j])$

转化为斜率方程为$f[j]-s[j]+ sb[j]*x[j] = x[i] * sb[j] +f[i]-c[i]-s[i]$

之后就套路上板子就可以了。

首先把不符合条件的队首T掉，之后用最新的队首更新f[i]，之后维护凸包性质把加入i后不满足的点T掉，最后加入i.

时间复杂度O(n)。

#include <cstdio>
#define y(j) (f[j]-s[j]+sb[j]*x[j])
int n,h,t;
long long x[1000010],p[1000010],c[1000010],f[1000010],q[1000010],s[1000010],sb[1000010];
void init()
{
    long long tmp=0;
    for(int i=1;i<=n;++i)
    {
        sb[i]=sb[i-1]+p[i];
        tmp+=p[i-1];
        s[i]=s[i-1]+tmp*(x[i]-x[i-1]);
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld%lld%lld",x+i,p+i,c+i);
    init();
    for(int i=1;i<=n;++i)
    {
        while(h<t&&(y(q[h+1])-y(q[h]))<x[i]*(sb[q[h+1]]-sb[q[h]])) ++h;
        f[i]=f[q[h]]+c[i]+s[i]-s[q[h]]-sb[q[h]]*x[i]+sb[q[h]]*x[q[h]];
        while(h<t&&(y(i)-y(q[t]))*(sb[q[t]]-sb[q[t-1]])<(sb[i]-sb[q[t]])*(y(q[t])-y(q[t-1]))) --t;
        q[++t]=i;
    }
    printf("%lld",f[n]);
}
//f[j]-s[j]+ sb[j]*x[j] = x[i] * sb[j] +f[i]-c[i]-s[i]