任务安排2

AcWing-301-任务安排2

分析

见《进阶指南》第323页。

实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 300010;
int n, s;
int h = 1, t, q[N];
LL f[N], st[N], sc[N];

int main () {
    cin >> n >> s;
    for (int i = 1, t, c; i <= n; ++ i) {
        cin >> t >> c;
        st[i] = st[i - 1] + t;
        sc[i] = sc[i - 1] + c;
    }

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    q[++ t] = 0;
    for (int i = 1; i <= n; ++ i) {
        while (h < t
            && (f[q[h + 1]] - f[q[h]])
            <= (s + st[i]) * (sc[q[h + 1]] - sc[q[h]])
        ) {
            ++ h;
        }
        f[i] = f[q[h]] - (s + st[i]) * sc[q[h]] + st[i] * sc[i] + s * sc[n];
        while (h < t
            && (f[q[t]] - f[q[t - 1]]) * (sc[i] - sc[q[t]])
            >= (f[i] - f[q[t]]) * (sc[q[t]] - sc[q[t - 1]])
        ) {
            -- t;
        }
        q[++ t] = i;
    }
    cout << f[n] << endl;
    return 0;
}