运输小猫

AcWing-303-运输小猫

分析

见《进阶指南》第328页。

实现

#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;

typedef long long LL;
const int N = 100010, M = 110;
int n, m, p;
LL sd[N], a[N], sa[N], f[M][N], g[N];
int h, t, q[N];

int main () {
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 2, d; i <= n; ++ i) {
        scanf("%d", &d);
        sd[i] = sd[i - 1] + d;
    }
    for (int i = 1, h, t; i <= m; ++ i) {
        scanf("%d%d", &h, &t);
        a[i] = t - sd[h];
    }

    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; ++ i) sa[i] = sa[i - 1] + a[i];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= p; ++ i) {
        for (int j = 1; j <= m; ++ j)
            g[j] = f[i - 1][j] + sa[j];
        h = 1, t = 0;
        q[++ t] = 0;
        for (int j = 1; j <= m; ++ j) {
            while (h < t && g[q[h + 1]] - g[q[h]] <= a[j] * (q[h + 1] - q[h])) ++ h;
            f[i][j] = min(f[i - 1][j], g[q[h]] + a[j] * (j - q[h]) - sa[j]);
            if (g[j] >= inf) continue;
            while (h < t
                && (g[j] - g[q[t]]) * (q[t] - q[t - 1])
                <= (g[q[t]] - g[q[t - 1]]) * (j - q[t])
            ) {
                -- t;
            }
            q[++ t] = j;
        }
    }
    printf("%lld", f[p][m]);
    return 0;
}