洛谷2120 [ZJOI2007]仓库建设

题意

有 $N$ 个工厂，每个工厂与第 $1$ 个工厂的距离为 $X_i$，有成品 $P_i$ 件。需要修建一些仓库，在每个工厂修建的成本为 $C_i$ 。

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

$N\le 10^6$ 。

题解

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

$$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] = \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) )$$

令 $SP_i = \sum_{j=1}^i P_j \ , \ S_i = \sum_{j=1}^i X_i \times P_i$ ：

$$f[i] = \min_{j=0}^{i-1} ( f[j] + C_i + X_i \times (SP_{i-1} - SP_j) - S_{i-1} + S_j )$$

有 $i$ 和 $j$ 的乘积，考虑斜率优化：

$$f[j] + S_j = X_i \times SP_j + ( S_{i-1} - X_i \times SP_{i-1} - C_i )$$

斜率 $X_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]);
}