2021牛客多校2 G League of Legends

题目描述

https://ac.nowcoder.com/acm/contest/11253/G

简要题意：给定 $n$ 个区间和 $k$，求将所有区间划分成 $k$ 组的最大价值和，每组区间的价值为它们的交，交不能为空，如果无法划分输出 $-1$

$1\le k\le n\le 5000$

Solution

我们考虑如果按照左端点排序后，保证右端点递增的话，那么一定是相邻的若干个放到一组

然后我们发现，如果右端点不递增，那么说明当前区间被其它区间完全包含，显然如果一个区间完全包含另一个区间，那么这个大区间跟这个小区间放到一起后肯定是没用的，如果和别的区间放一组，只会使答案减少

所以我们先把大区间都拿出来，表示是否单独放一组

然后这个时候我们左右端点都是递增的，我们就可以做 $dp$ 了

令 $f[i][j]$ 表示前 $j$ 个分了 $i$ 组，转移 $f[i][j]=f[i-1][k]+r[k+1]-l[j]$，且需保证 $r[k+1]\ge l[j]$

然后我们发现这是一个典型的单调队列优化 $dp$

时间复杂度 $O(n^2)$

#include <iostream>
#include <queue>
#include <algorithm>
#define maxn 5010
#define INF 1000000000
using namespace std;

int n, m;

struct node {
    int x, y; 
} a[maxn], b[maxn]; int cnt;

int Q[maxn], h, t;

int f[maxn][maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> b[i].x >> b[i].y;
    sort(b + 1, b + n + 1, [](const node &u, const node &v) { return u.x == v.x ? u.y < v.y : u.x < v.x; });
    priority_queue<int> H; 
    for (int i = 1; i <= n; ++i) {
        while (cnt && b[i].y <= a[cnt].y) {
            H.push(a[cnt].y - a[cnt].x);
            --cnt;
        } a[++cnt] = b[i];
    }
    for (int i = 0; i <= n; ++i) f[0][i] = -INF; f[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
        Q[h = t = 1] = 0;
        for (int j = 1; j <= cnt; ++j) {
            while (h < t && a[Q[h] + 1].y < a[j].x) ++h;
            f[i][j] = f[i - 1][Q[h]] + a[Q[h] + 1].y - a[j].x;
            while (h <= t && f[i - 1][Q[t]] + a[Q[t] + 1].y <= f[i - 1][j] + a[j + 1].y) --t;
            Q[++t] = j;
        }
    }
    int num = 0, sum = 0, ans = f[m][cnt];
    while (!H.empty()) {
        sum += H.top(); H.pop(); ++num;
        if (num > m) break; 
        ans = max(ans, f[m - num][cnt] + sum); 
    }
    if (ans < 0) cout << 0 << "\n";
    else cout << ans << "\n";
    return 0;
}