这题还蛮简单的。

洛谷通道

设 $f_i$ 表示强制建 $i$ 以保护 $[1,i]$ 物品的最小代价。
则容易写出状态转移方程，枚举上一次在 $j$ 建立仓库：

$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + c_i + (\sum\limits_{k=j+1}^{i-1} (x_i - x_k) \times p_k) \}$$

把式子拆一下，得到：

$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + ( \sum\limits_{k=j+1}^{i-1} p_k ) \times x_i - (\sum\limits_{k=j+1}^{i-1} x_k \times p_k) \} + c_i$$

设 $sp$ 为 $p$ 前缀和，$s$ 为 $x \times p$ 前缀和。

$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + (sp_{i-1} - sp_j) - (s_{i-1} - s_j) \} + c_i$$

于是又是一波推斜率优化，套路。
然后得到：

$$x_i \leq \frac{(f_{j_1} + s_{j_1})-(f_{j_2} + s_{j_2})}{sp_{j_1} - sp_{j_2}}$$

另外 acw 数据太弱，这里提供一组 hack 数据（已被管理加入评测数据）。

input

5
0 0 5
3 1 2
5 0 3
7 9 2
9 0 1

answer

4

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
int n, x[N], p[N], c[N];
long long dp[N], sp[N], s[N];

long long X(int p) { return sp[p]; }
long long Y(int p) { return dp[p] + s[p]; }
long double slope(int a, int b) {
    if (X(a) == X(b)) {
        if (Y(a) == Y(b)) return 0;
        else if (Y(a) < Y(b)) return 1e18;
        else return -1e18;
    }
    return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));
}

int q[N], st, ed;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x[i], &p[i], &c[i]);
        sp[i] = sp[i - 1] + p[i];
        s[i] = s[i - 1] + x[i] * 1ll * p[i];
    }
    st = ed = 1, q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while (st < ed && slope(q[st], q[st + 1]) <= x[i]) st++;
        int j = q[st];
        dp[i] = dp[j] + x[i] * 1ll * (sp[i - 1] - sp[j]) - (s[i - 1] - s[j]) + c[i];
        if (p[i] == 0) dp[i] = min(dp[i], dp[i - 1]);
        while (st < ed && slope(q[ed - 1], q[ed]) >= slope(q[ed], i)) ed--;
        q[++ed] = i;
    }
    printf("%lld\n", dp[n]);
    return 0;
}