Cats Transport

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2527 字
P个饲养员从1号山出发接M只猫，求所有猫等待
一本通
例
正文

/*
原题：Cats Transport（一本通 5.6 例 4，CF Round #185 Div1 B）
题意：P 个饲养员从 1 号山出发接 M 只猫，求所有猫等待时间总和的最小值。
思路：r_i=T_i-A[H_i] 排序；dp[k][i] 表示 k 个饲养员接前 i 只猫的最小等待，化为斜率优化。
复杂度：O(P·M) 时间 / O(M) 空间
易错点：每个饲养员接连续一段，出发时刻取该段最大 r_i，等待=段长·r_末-Σr。
易错点：滚动数组；仅当 dp_prev[j] 有效（<INF）才加入凸包直线，空凸包时跳过查询。
*/
#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, M, P;
    if(!(cin >> N >> M >> P)) return 0;
    vector<long long> A(N + 1, 0);
    for(int i = 2; i <= N; i++){
        long long d;
        cin >> d;
        A[i] = A[i - 1] + d;
    }
    vector<long long> r(M + 1);
    for(int i = 1; i <= M; i++){
        long long h, t;
        cin >> h >> t;
        r[i] = t - A[h];
    }
    sort(r.begin() + 1, r.end());
    vector<long long> s(M + 1, 0);
    for(int i = 1; i <= M; i++) s[i] = s[i - 1] + r[i];
    const long long INF = 4e18;
    vector<long long> dp(M + 1, INF);
    dp[0] = 0;
    int layers = min(P, M);
    for(int k = 1; k <= layers; k++){
        vector<long long> ndp(M + 1, INF);
        CHT cht(true);
        cht.add(0, -(dp[0] + s[0]));
        for(int i = 1; i <= M; i++){
            if(!cht.q.empty()){
                long long maxv = cht.query(r[i]);
                ndp[i] = r[i] * i - s[i] - maxv;
            }
            if(dp[i] < INF) cht.add(i, -(dp[i] + s[i]));
        }
        dp = ndp;
    }
    cout << dp[M] << "\n";
    return 0;
}
Cats Transport

正文

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