洛谷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;
}