算法

(斜率优化dp) $O(n)$

记 dp[i] 表示在第 $i$ 个工厂建立仓库产生的最小费用。

状态转移：

$$ dp[i] = \min\{dp[j] + w(j, i) \big| 1 \leqslant j < i\} + c_i $$

$ \begin{aligned} w(j, i) &= p_{j+1} \times (x_i - x_{j+1}) + p_{j+2} \times (x_i - x_{j+2}) + \cdots + p_{i-1} \times (x_i - x_{i-1}) + p_i \times (x_i - x_i)\\\ &= x_i \times \sum_{k=j+1}^i p_k - \sum_{k=j+1}^{i} p_kx_k \end{aligned} $

我们用 $P_i$ 表示 $p_1 + p_2 + \cdots + p_i$，用 $Q_i$ 表示 $p_1x_1 + p_2x_2 + \cdots + p_ix_i$
那么 $w(j, i) = x_i(P_i-P_j) - (Q_i-Q_j)$

于是，$dp[i] = \min\{-P_jx_i + (dp[j] + Q_j)\} + P_ix_i - Q_i + c_i$

注意到斜率 $-P_j$ 单调递减，所以可以暴力移指针；另外，横坐标 $x_i$ 单调递增，所以可以用单调队列来维护凸包

还需注意以下坑点：

• 这里的 $dp$ 是假定在第 $i$ 个工厂建仓库，但最后一个工厂如果没有成品的话，就不需要建仓库了。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

template<class T=int>
inline T read() {
    T num = 0;
    int neg = 1;
    char c = getchar_unlocked();
    while (!isdigit(c) and c != '-') {
        c = getchar_unlocked();
    } 
    if (c == '-') neg = -1;
    else num = c-'0';
    c = getchar_unlocked();
    while (isdigit(c)) {
        num = (num<<1)+(num<<3)+(c^48);
        c = getchar_unlocked();
    }
    return num*neg;
}

// 求最小值
struct CHT {
    deque<P> d;
    void add(ll a, ll b) {
        while (d.size() >= 2) {
            auto [a1, b1] = d[d.size()-1];
            auto [a0, b0] = d[d.size()-2];
            if ((b0-b1)*(a-a1) < (b1-b)*(a1-a0)) break;
            d.pop_back();
        }
        d.emplace_back(a, b);
    }
    ll get(ll x) {
        while (d.size() >= 2) {
            auto [a0, b0] = d[0];
            auto [a1, b1] = d[1];
            if (a0*x+b0 < a1*x+b1) break;
            d.pop_front();
        }
        auto [a, b] = d[0];
        return a*x+b;
    }
};

int main() {
    int n = read();

    vector<ll> x(n), p(n), c(n);
    rep(i, n) x[i] = read<ll>(), p[i] = read<ll>(), c[i] = read<ll>();

    auto P = p;
    rep(i, n-1) P[i+1] += P[i];
    vector<ll> Q(n);
    rep(i, n) Q[i] = p[i]*x[i];
    rep(i, n-1) Q[i+1] += Q[i];

    ll ans = 0;
    CHT cht;
    cht.add(0, 0);
    rep(i, n) {
        ans = cht.get(x[i]);
        ans += P[i]*x[i] - Q[i] + c[i];
        cht.add(-P[i], ans+Q[i]);
    }
    if (p[n-1] == 0) ans -= c[n-1];

    cout << ans << '\n';

    return 0;
}