围栏

AcWing-298-围栏

分析

见《进阶指南》第314页。

实现

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 16010, M = 110;
struct node {
    int l, p, s;
    bool operator < (const node& o) const {
        return s < o.s;
    }
};
int n, m;
node a[M];
deque<int> dq;
int f[M][N];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i) cin >> a[i].l >> a[i].p >> a[i].s;

    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; ++ i) {
        for (int j = 0; j <= n; ++ j) {
            f[i][j] = f[i - 1][j];
            if (j >= 1) f[i][j] = max(f[i][j], f[i][j - 1]);

            int l = a[i].l, p = a[i].p, s = a[i].s;
            if (!dq.empty() && dq.front() < j - l) dq.pop_front();
            if (j >= s && !dq.empty()) {
                int k = dq.front();
                f[i][j] = max(f[i][j], f[i - 1][k] + (j - k) * p);
            }
            if (j < s) {
                while (!dq.empty()
                    && f[i - 1][dq.back()] - dq.back() * p <= f[i - 1][j] - j * p
                ) {
                    dq.pop_back();
                }
                dq.push_back(j);
            }
        }
    }
    cout << f[m][n] << endl;
    return 0;
}