题解 | #League of Legends#

G - League of Legends

题意：
有个人，要分组，每个人有自己的空闲时间，一个组里可玩耍的时间是组内所有人时间的交集，要求至少为。问最优情况下，所有组能玩耍的时间之和最大是多少。

思路：
我们发现能覆盖别的小区间的大区间十分特殊。如果和别人放在一起，大区间一定会覆盖组内的交集，可以看做对答案没有贡献；如果单独放为一组，贡献就很大了。所以考虑优先处理大区间，把它们筛出来，可以求出将个大区间单独设为组能取得的最大贡献。

对于剩下来的小区间，我们转换一下，每个组的贡献就是每个组之中最小的右端点减去最大的左端点，且贡献一定要大于。我们先按左端点进行排序，再按右端点排序（其实右端点的排序是多余的，因为能覆盖的大区间已经删去了，所以不会有重复的左右端点了）。设为将前个人分成组的最大玩耍时间，马上能写出一个的转移方程，因为我们并不知道新开的组的开头在哪儿，结尾也要去找，然后更新。

的就是当前的结尾位置，所以这一步应该是优化不掉的，考虑优化开头。结尾的人的左端点一定是最大的，前面如果有多个人的右端点比当前左端点大，那么最优考虑肯定会选离当前这个人最远的人作为开头。这一步就可以用单调队列来实现了，两个单调队列，一个用于判断左右端点的条件，同时我们需要用另一个来存来体现转移的过程，将当前决策和之前的最优决策结合起来，一起考虑。将第二个单调队列里的值取出来，减去当前结尾的左端点就是当前的答案了。

#include <bits/stdc++.h>

using namespace std;

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 7;

int n, k;
int dp[N][N], sum[N];

struct Interval {
    int x, y, big;
}t[N], fa[N];

bool cmpPre(Interval a, Interval b) {
    if (a.big != b.big) return a.big < b.big;
    return a.x < b.x;
}

bool cmpSuf(Interval a, Interval b) {
    return a.y - a.x > b.y - b.x;
}

void solve() {
    n = rd(), k = rd();
    int tot = n;
    for (int i = 1; i <= n; ++i) {
        t[i].x = rd(), t[i].y = rd(), t[i].big = 0;
    }
    int numBig = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j || t[j].big) continue;
            if (t[i].x <= t[j].x && t[i].y >= t[j].y) {
                t[i].big = 1;
                fa[++numBig] = t[i];
                break;
            }
        }
    }
    sort(t + 1, t + 1 + n, cmpPre);
    n -= numBig; 
    sort(fa + 1, fa + 1 + numBig, cmpSuf);

    memset(sum, -0x3f, sizeof(sum));
    sum[0] = 0;
    for (int i = 1; i <= numBig; ++i) {
        sum[i] = fa[i].y - fa[i].x + sum[i - 1];
    }

    memset(dp, -0x3f, sizeof(dp));
    for (int i = 1; i <= n; ++i) {
        if (t[1].y > t[i].x) dp[i][1] = t[1].y - t[i].x; // at least one
    }
    vector<int> qy(n + 1), qw(n + 1);
    for (int j = 2; j <= k; ++j) {
        int head = 1, tail = 0;
        qy[++tail] = t[j].y;
        qw[tail] = dp[j - 1][j - 1] + t[j].y;
        for (int i = j; i <= n; ++i) {
            while (head <= tail && qy[head] <= t[i].x) head++;
            if (head <= tail) dp[i][j] = qw[head] - t[i].x;
            int y = t[i + 1].y;
            if (dp[i][j - 1] <= 0) continue;
            while (head <= tail && qw[tail] <= dp[i][j - 1] + t[i + 1].y) tail--; // dp[k][j - 1] + t[k + 1].y, k < i
            qy[++tail] = t[i + 1].y;
            qw[tail] = dp[i][j - 1] + t[i + 1].y;
        }
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
        ans = max(ans, dp[n][i] + sum[k - i]);
    }
    printf("%d\n", ans);
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}