仓库建设

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2140 字
N个工厂，产品只能往山下运，选若干建仓库，求
一本通
练习
正文

/*
原题：仓库建设（一本通 5.6 练习 2，ZJOI 2007）
题意：N 个工厂，产品只能往山下（编号更大）运，选若干建仓库，求建造+运输最小费用。
思路：dp[i]=min{dp[j]+C_i+X_i(sP[i-1]-sP[j])-(B[i-1]-B[j])}；化为 max 直线斜率 sP[j]、截距 -(dp[j]+B[j])。
复杂度：O(N) 时间 / O(N) 空间
易错点：B[i]=ΣP_k·X_k 前缀和，单段运输费=ΣP_k(X_i-X_k)=X_i(sP)-B。
易错点：查询点 X_i，求 max；j=0 对应「前面全运到第 i 厂」，截距为 0。
*/
#include <bits/stdc++.h>
using namespace std;
struct Line {
    long long m, b;
    long long eval(long long x) const {
        return m * x + b;
    }
};
struct CHT {
    bool isMax;
    deque<Line> q;
    CHT(bool mx) : isMax(mx) {}
    bool bad(const Line& l1, const Line& l2, const Line& l3) const {
        __int128 A = (__int128)(l2.b - l1.b) * (l2.m - l3.m);
        __int128 B = (__int128)(l3.b - l2.b) * (l1.m - l2.m);
        return isMax ? (A >= B) : (A <= B);
    }
    void add(long long m, long long b){
        Line l = {m, b};
        if(!q.empty() && q.back().m == m){
            if(isMax ? (l.b <= q.back().b) : (l.b >= q.back().b)) return;
            q.pop_back();
        }
        while(q.size() >= 2 && bad(q[q.size() - 2], q.back(), l)) q.pop_back();
        q.push_back(l);
    }
    long long query(long long x){
        int lo = 0, hi = (int)q.size() - 1;
        while(hi > lo){
            int mid = (lo + hi) / 2;
            long long v1 = q[mid].eval(x), v2 = q[mid + 1].eval(x);
            if(isMax ? (v2 > v1) : (v2 < v1)) lo = mid + 1;
            else hi = mid;
        }
        return q[lo].eval(x);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if(!(cin >> N)) return 0;
    vector<long long> X(N + 1), P(N + 1), C(N + 1);
    for(int i = 1; i <= N; i++) cin >> X[i] >> P[i] >> C[i];
    vector<long long> sP(N + 1, 0), B(N + 1, 0);
    for(int i = 1; i <= N; i++){
        sP[i] = sP[i - 1] + P[i];
        B[i] = B[i - 1] + P[i] * X[i];
    }
    vector<long long> dp(N + 1, 0);
    CHT cht(true);
    cht.add(sP[0], -(dp[0] + B[0]));
    for(int i = 1; i <= N; i++){
        long long maxv = cht.query(X[i]);
        dp[i] = C[i] + X[i] * sP[i - 1] - B[i - 1] - maxv;
        cht.add(sP[i], -(dp[i] + B[i]));
    }
    cout << dp[N] << "\n";
    return 0;
}
仓库建设

正文

一本通·提高篇的其它内容
