思路与算法

记S为库存前缀和，T为库存乘位置的前缀和。强制最后仓库在i的最优值f[i]=C[i]+X[i]S[i]-T[i]+min_{j<i}(f[j]+T[j]-X[i]S[j])。把j写成斜率-S[j]、截距f[j]+T[j]的直线，用单调凸包查询。位置递增、库存非负使查询点递增、斜率不增。最终只需最后仓库不早于最后一个有货工厂；零库存尾部可取相应f的最小值，不强制在N另建仓。

正确性说明

若前一个仓库是j，j+1至i的货物都送到i，运输和为Xi-(T[i]-T[j])，直接得到递推。每种仓库划分都被枚举，最优子结构成立。单调凸包删去交点次序错误的中间直线及同斜率劣线，未来不会最优；查询点递增时，已被下一线超过的首线也不会再最优。零库存后的工厂可以不建，最终最小化最后有货点之后的所有候选，覆盖完整题意。

复杂度

每条线至多入队、出队一次，时间O(N)、空间O(N)，输入与队列预留初始化也计入。N≤10^6，使用128位整数作线性表达式、自包含的三段64位整数作192位精确交叉乘积比较，不做浮点斜率；题目保证最终与原题中间费用在long long内，输出转64位。

易错点

库存为0时斜率可能相同，要保留较小截距。不能无条件返回f[N]：例0位置有1件且建仓费1、下一厂零库存费100，答案是1。独立小例枚举全部仓库子集；百万工厂统一成本10的下界10+L(L-1)/2≥4L与长度4或5分组给出精确最优4N。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using Wide = __int128;
struct Line {
    long long slope;
    Wide intercept;
};
Wide value(Line l, long long x) {
    return Wide(l.slope) * x + l.intercept;
}
using UnsignedWide = unsigned __int128;
struct SignedProduct {
    bool negative;
    unsigned long long high, middle, low;
};
SignedProduct multiplyExact(Wide number, long long factor) {
    bool negative = number < 0;
    UnsignedWide magnitude = negative ? UnsignedWide(-(number + 1)) + 1 : UnsignedWide(number);
    unsigned long long f = (unsigned long long)factor;
    UnsignedWide lower = UnsignedWide((unsigned long long)magnitude) * f;
    UnsignedWide upper = UnsignedWide((unsigned long long)(magnitude >> 64)) * f + (lower >> 64);
    return {negative && magnitude != 0 && f != 0, (unsigned long long)(upper >> 64),
            (unsigned long long)upper, (unsigned long long)lower};
}
bool productAtLeast(SignedProduct a, SignedProduct b) {
    if (a.negative != b.negative)
        return !a.negative;
    auto x = make_tuple(a.high, a.middle, a.low);
    auto y = make_tuple(b.high, b.middle, b.low);
    return a.negative ? x <= y : x >= y;
}
bool obsolete(Line a, Line b, Line c) {
    return productAtLeast(multiplyExact(b.intercept - a.intercept, b.slope - c.slope),
                          multiplyExact(c.intercept - b.intercept, a.slope - b.slope));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Line> q;
    q.reserve(n + 1);
    q.push_back({0, 0});
    size_t head = 0;
    long long S = 0;
    Wide T = 0, answer = 0;
    for (int i = 0; i < n; ++i) {
        long long x, p, c;
        cin >> x >> p >> c;
        S += p;
        T += Wide(x) * p;
        while (head + 1 < q.size() && value(q[head], x) >= value(q[head + 1], x))
            ++head;
        Wide f = value(q[head], x) + Wide(x) * S - T + c;
        if (p > 0)
            answer = f;
        else
            answer = min(answer, f);
        Line next = {-S, f + T};
        if (q.size() > head && q.back().slope == next.slope) {
            if (q.back().intercept <= next.intercept)
                continue;
            q.pop_back();
        }
        while (q.size() >= head + 2 && obsolete(q[q.size() - 2], q.back(), next))
            q.pop_back();
        q.push_back(next);
    }
    cout << (long long)answer << '\n';
}