P2120 [ZJOI2007] 仓库建设 题解

· · 题解

一道很标准的斜率 dp

简要题意

有 n 个工厂，坐标分别为 x_i（其中 x_1=0），每个工厂有 p_i 个产品，现需在其中建设几个仓库，第 i 个工厂建设为仓库的费用为 c_i，每个工厂都需要向坐标比自己大且距离最近的仓库运输全部产品，运输费用是产品数量与此工厂和仓库距离的乘积，求总运输费用的最小值。

转移方程

（对于最基础的 O(n^2) 递推式，建议先自行推导一遍）
首先，因为对于工厂 j 中的 p_j 个货物只能往编号更大的工厂仓库 i 运输，不难发现在 i 处建设仓库的费用可以由前面已建设仓库的总费用加上仓库 i 建设费用和新运输费用得到，即：

f_i = \textstyle \min_{k=1}^{i-1}( f_k + \textstyle \sum_{j=k+1}^{i} p_j\times(x_i-x_j) ) + c_i

然后照常把 \min 去掉，改成形如 y=kx+b 的形式：

f_i = f_k + \textstyle \sum_{j=k+1}^{i} p_j\times(x_i-x_j) + c_i = f_k + x_i\textstyle \sum_{j=k+1}^{i} p_j - \textstyle \sum_{j=k+1}^{i}p_j \times x_j + c_i

令 sump_i = \sum_{k=1}^{i} p_k， sumt_i = \sum_{k=1}^{i} p_k\times x_k

f_i = f_k + x_i\times (sump_i-sump_k) - (sumt_i-sumt_k) + c_i = f_k +sumt_k +c_i + x_i\times sump_i - x_i\times sump_k - sumt_i

将只与 k 有关的项放在左边，只与 i 有关的项放在右边，同时带有 i 和 k 的项中以与 i 有关的参数作为斜率，得：

f_k + sumt_k = x_i\times sump_k + f_i - c_i + sumt_i - x_i\times sump_i

即：

y=f_k + sumt_k k=x_i x=sump_k b=f_i - c_i + sumt_i - x_i\times sump_i

接下来就是套斜率 dp 板子了
本题需要求费用即 f_n 的最小值，枚举 i，用队列对处理过的工厂 k 记录的散点 (sump_k,f_k+sumt_k) 维护一个第一条线的斜率总大于当前斜率 k=x_i 的下凸壳，每次维护后用队列中第一个点转移即可，转移后将 (sump_i,f_i+sumt_k) 插入到队尾，若此时不能满足队列中散点间斜率单调递增，则弹出队列中 i 前的一个点，以此类推。
时间复杂度 O(n)

小细节

CODE

//请千万不要试图直接提交此代码！

/*
    f[i] = min( f[k] + c_i + sigma( p_p * dis_p..i ) ){i>=p>k}
         = f[k] + c_i + sigma( p_p * ( x_i - x_p ) )
         = f[k] + c_i - sigma( p_p * x_p ) + x_i * sigma( p_p )
    let sumt_i = sigma( p_i * x_i ) , s_i = sigma( p_i );
=>  f[i] = f[k] + c_i - ( sumt[i] - sumt[k] ) + x_i * ( s[i] - s[k] );
         = f[k] + c_i - sumt[i] +sumt[k] + x_i * s[i] - x_i * s[k];
=>  f[k] + sumt[k] = x_i * s[k] + f[i] - c_i + sumt[i] - x_i * s[i];
    ~~~~~~~~~~~~   ~~~   ~~~~   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
          y      =  k  *  x   +               b
*/

const int N=1e6+5;
long long n;
long long x[N],p[N],c[N];
long long sumt[N],sump[N];
long long f[N];
long long q[N];
int l,r;

double Y(int i){
    return f[i] + sumt[i];
}

double X(int i){
    return sump[i];
}

double slope(int i,int j){
    if (X(i)==X(j)) return (Y(i)-Y(j))>0?-1e18:1e18;
    return (Y(i)-Y(j))/(X(i)-X(j));
}

signed mаin(){
    scаnf("%lld",&n);
    for (int i=1;i<=n;i++) scаnf("%lld%lld%lld",x+i,p+i,c+i);
    for (int i=1;i<=n;i++) sumt[i]=p[i]*x[i] + sumt[i-1], sump[i]= p[i] + sump[i-1];
    l=r=1;
    for (int i=1;i<=n;i++){
        while(l<r&&slope(q[l],q[l+1])<=x[i]) l++;
        int k=q[l];
        f[i]=f[k] + c[i] - ( sumt[i] - sumt[k] ) + x[i] * ( sump[i] - sump[k] );
        while(l<r&&(slope(q[r],q[r-1])>=slope(q[r],i))) r--;
        q[++r] = i;
    }
    long long аns=0x3f3f3f3f3f3f;
    for(int i=n;i>=1;i--){
        аns=min(аns,f[i]);
        if(p[i])breаk;
    }
    printf("%lld\n",аns);

    return QWQ;
}