洛谷P2120 [ZJOI2007] 仓库建设题解

题目链接：P2120 [ZJOI2007] 仓库建设

题意：

L 公司有 \(n\) 个工厂，由高到低分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚。

由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 \(i\) 个工厂目前已有成品 \(p_i\) 件，在第 \(i\) 个工厂位置建立仓库的费用是 \(c_i\)。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 \(n\)，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 \(1\)。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

工厂 \(i\) 距离工厂 \(1\) 的距离 \(x_i\)（其中 \(x_1=0\)）。

工厂 \(i\) 目前已有成品数量 \(p_i\)。

在工厂 \(i\) 建立仓库的费用 \(c_i\)。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。

输入格式：

输入的第一行是一个整数 \(n\)，代表工厂的个数。

第 \(2\) 到 \((n + 1)\) 行，每行有三个用空格隔开的整数，第 \((i + 1)\) 行的整数依次代表 \(x_i,~p_i,~c_i\)。

输出格式：

仅输出一行一个整数，代表最优方案的费用。

数据范围：

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(0 \leq x_i,p_i,c_i < 2^{31}\)。

对于任意的 \(1 \leq i < n\)，保证 \(x_i < x_{i + 1}\)。设答案为 \(ans\)，保证 \(ans + \sum_{i = 1}^{n} p_ix_i < 2^{63}\)。

设 \(f_i\) 表示考虑前 \(i\) 个位置并且钦定 \(i\) 必须建工厂时的最小花费，则 \[ f_i=\min _{0 \leq j<i}\left\{f_j+\sum_{k=j+1}^i(x_i-x_k) p_k\right\}+c_i \] 考虑前缀和优化。记 \(s_i = \sum_{k=1}^ip_k,S_i = \sum_{k=1}^ix_kp_k\) ，那么 \[ f_i=\min _{0 \leq j<i}\left\{f_j+x_i(s_i-s_j)-(S_i-S_j)\right\}+c_i \] 继续考虑斜率优化。

考察 \(0 \le j < k < i\) 时，若 \(k\) 比 \(j\) 更优则有 \[ f_k+x_i\left(s_i-s_k\right)-\left(S_i-S_k\right)<f_j+x_i\left(s_i-s_j\right)-\left(S_i-S_j\right) \] 整理得 \[ (f_k + S_k) - (f_j + S_j) < x_i(s_k - s_j) \] 直接用单调队列维护即可。注意这个题会有 \(p_i=0\) 的情况。

那么答案就是最后一个 \(p_i\ne 0\) 的位置到 \(n\) 之间的 \(f\) 的最小值。如果没有任何货物答案则为 \(0\) 。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int st, en, p[N], q[N], x[N], c[N], s[N], f[N], S[N];
#define x(t) (s[t])
#define y(t) (f[t] + S[t])
bool test1(int i, int z)
{
    int now = q[z], nxt = q[z + 1];
    return y(nxt) - y(now) < x[i] * (x(nxt) - x(now));
}
bool test2(int i, int z)
{
    int now = q[z], pre = q[z - 1];
    return (y(i) - y(now)) * (x(now) - x(pre)) <= (x(i) - x(now)) * (y(now) - y(pre));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 1, n)
    {
        cin >> x[i] >> p[i] >> c[i];
        s[i] = s[i - 1] + p[i]; S[i] = S[i - 1] + x[i] * p[i];
    }
    q[en = 1] = f[0] = 0;
    rep(i, 1, n)
    {
        while(st + 1 < en && test1(i, st + 1)) ++st;
        int &j = q[st + 1]; f[i] = f[j] + x[i] * (s[i] - s[j]) - (S[i] - S[j]) + c[i];
        while(st + 1 < en && test2(i, en)) --en;
        q[++en] = i;
    }
    int res = INF;
    Rep(i, n, 0) { down(res, f[i]); if(p[i]) break; }
    cout << res << '\n';
    return 0;
}