L 公司有 $N$ 个工厂，由高到底分布在一座山上。工厂 $1$ 在山顶，工厂 $N$ 在山脚。由于这座山处于高原内陆地区 (干燥少雨)，L 公司一般把产品直接堆放在露天，以节省费用。

突然有一天，L 公司的总裁 scx 接到气象部门的电话，被告知三天之后将有一场暴雨，于是 scx 决定紧急在某些工厂建立一些仓库以免产品被淋坏。

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

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 $L$ 公司产品的对外销售处设置在山脚的工厂 $N$，故产品只能往山下运 (即只能运往编号更大的工厂的仓库)。

当然运送产品也是需要费用的，假设一件产品运送 $1$ 个单位距离的费用是 $1$。假设建立的仓库容量都都是足够大的，可以容下所有的产品。

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

输入格式

接下来 $N$ 行，每行包含三个非负整数 $X_i, P_i, C_i$ ($X_i, P_i, C_i < 2^{31}$)，意义如题中所述。

输出格式

题解

容易想到 DP。记 $f_i$ 表示在前 $i$ 个工厂中选建仓库，其中第 $i$ 个工厂建仓库，($1 \sim i$) 所需的最小费用。容易得到如下 DP 方程：$$ f_i = \min_{0 \leq j < i} \left\{ f_j + \sum_{k=j+1}^i (X_i - X_k) P_k \right\} + C_i $$

时间复杂度 $O(n^3)$，显然进行前缀和优化，记 $s_i = \sum\limits_{k=1}^i P_k, S_i = \sum\limits_{k=1}^i X_k P_k$，则原方程即 $$ f_i = \min_{0 \leq j < i} \left\{ f_j + X_i (s_i - s_j) - (S_i - S_j) \right\} + C_i $$

于是时间复杂度变为 $O(n^2)$，依然过不去。考虑到有两个值相减的形式，于是尝试进行斜率优化：

考虑 $0 \leq j < k < i$，于是 $s_j < s_k, S_j < S_k$，假设 $k$ 的决策比 $j$ 更优 (即 $f_k + X_i (s_i - s_k) - (S_i - S_k) < f_j + X_i (s_i - s_j) - (S_i - S_j)$)，化简即得 $$ (f_k + S_k) - (f_j + S_j) < X_i (s_k - s_j) $$

记点 $p_i = (x_i, y_i) = (s_i, f_i + S_i)$，那么上式可化为 $\dfrac {y_j - y_k} {x_j - x_k} < X_i$，是一个经典的斜率方程，直接用单调队列即可。时间复杂度 $O(n)$，最后答案即为 $f_n$ (因为最后一个对外销售的工厂是必须建立仓库的)。

代码

#include <bits/stdc++.h>
#define N 1024404
#define y(_) (f[_] + S[_])
#define x(_) (s[_])
using namespace std;

typedef long long ll;

int n, i, j;
ll p, x[N], c[N], s[N], S[N], f[N];
int h, t, que[N];

inline bool test1(int i, int z){
    int now = que[z], next = que[z + 1];
    return y(next) - y(now) < x[i] * (x(next) - x(now));
}

inline bool test2(int i, int z){
    int now = que[z - 1], prev = que[z - 2];
    return (y(i) - y(now)) * (x(now) - x(prev)) <= (x(i) - x(now)) * (y(now) - y(prev));
}

int main(){
    scanf("%d", &n);
    for(i = 1; i <= n; ++i){
        scanf("%lld%lld%lld", x + i, &p, c + i);
        s[i] = s[i - 1] + p; S[i] = S[i - 1] + x[i] * p;
    }
    h = 0; t = 1;
    que[0] = f[0] = 0;
    for(i = 1; i <= n; ++i){
        for(; h < t - 1 && test1(i, h); ++h);
        j = que[h];
        f[i] = f[j] + x[i] * (s[i] - s[j]) - (S[i] - S[j]) + c[i];
        for(; h + 1 < t && test2(i, t); --t);
        que[t++] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

题目描述

输入格式

输出格式

题解

代码

坑