洛谷2120 [ZJOI2007]仓库建设

编辑文章

题意

NN 个工厂,每个工厂与第 11 个工厂的距离为 XiX_i,有成品 PiP_i 件。需要修建一些仓库,在每个工厂修建的成本为 CiC_i

修建完成后要将成品全部运到仓库里,且只能往序号较大的工厂里运输。运输的成本为 Pi×(XjXi)P_i\times (X_j-X_i) 。求成本的最小值。

N106N\le 10^6

题解

f[i]f[i] 表示最后在 ii 修仓库的最小成本,枚举上一次修仓库的位置 jj ,需要将 [j+1,i1][j+1,i-1] 的成品都送到 ii 。方程式为:

f[i]=minj=0i1(f[j]+Ci+k=j+1i1Pk×(XiXk))f[i] = \min_{j=0}^{i-1} ( f[j] + C_i + \sum_{k=j+1}^{i-1} P_k \times (X_i - X_k) )

f[i]=minj=0i1(f[j]+Ci+k=j+1i1(Pk×XiPk×Xk))f[i] = \min_{j=0}^{i-1} ( f[j] + C_i + \sum_{k=j+1}^{i-1} ( P_k \times X_i - P_k \times X_k) )

SPi=j=1iPj , Si=j=1iXi×PiSP_i = \sum_{j=1}^i P_j \ , \ S_i = \sum_{j=1}^i X_i \times P_i

f[i]=minj=0i1(f[j]+Ci+Xi×(SPi1SPj)Si1+Sj)f[i] = \min_{j=0}^{i-1} ( f[j] + C_i + X_i \times (SP_{i-1} - SP_j) - S_{i-1} + S_j )

iijj 的乘积,考虑斜率优化:

f[j]+Sj=Xi×SPj+(Si1Xi×SPi1Ci)f[j] + S_j = X_i \times SP_j + ( S_{i-1} - X_i \times SP_{i-1} - C_i )

斜率 XiX_i 显然单调。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const int N=1000005;
ll n,x[N],p[N],c[N],s[N],q[N],f[N];

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++)
    {
        x[i]=read();
        p[i]=read();
        s[i]=s[i-1]+x[i]*p[i];
        p[i]+=p[i-1];
        c[i]=read();
    }
    ll l=1,r=1; q[l]=0;
    for (ll i=1;i<=n;i++)
    {
        while (l<r && f[q[l+1]]+s[q[l+1]]-f[q[l]]-s[q[l]]
               <=(p[q[l+1]]-p[q[l]])*x[i]) l++;
        f[i]=f[q[l]]+x[i]*(p[i-1]-p[q[l]])-s[i-1]+s[q[l]]+c[i];
        while (l<r && (f[q[r]]+s[q[r]]-f[q[r-1]]-s[q[r-1]])*(p[i]-p[q[r]])
               >=(f[i]+s[i]-f[q[r]]-s[q[r]])*(p[q[r]]-p[q[r-1]])) r--;
        q[++r]=i;
    }
    return !printf("%lld",f[n]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空