多校第二场League of Legends

题目描述:n<=5000的人分成k组打游戏，[ai,bi)是每个人的空闲时间，每组至少有一个人，每个人都加入一组，每组至少玩一个单位时间，求所有组玩游戏时间总和最大。
相当于把n个区间分成k组，每组求交集，k个交集之和最大。
对于区间我们可以先按左端点排序，对于"大区间"（覆盖小区间的区间）可以单独自己在一组，或是和小区间在一起(此时有大区间和没大区间对答案无影响，因此只需关注小区间),(而和其他区间在一起至少会使合法长度降低,因此在最优方案中没有这种)。因此我们可以把大区间单独拎出来，单独排序，选前i长的区间之和
不妨设sum[i]表示上前i个最大的大区间之和,ans=max{sum[i]+dp[n][k-i]}
为了求解dp我们做：
设前i个小区间分为j组的最优值为dp[i][j]
因为必定为连续的若干分到一组
dp[i][j]= {dp[k][j-1]+b[k+1]-a[i]} 且b[k+1]>a[i]
=-a[i]+max{dp[k][j-1]+b[k+1]}（b[k+1]>a[i]）
而满足b[k+1]>a[i]的必然是前面的一段连续区间，求连续区间的最大值可以用单调队列来优化。转移可以做到o（1）然后在枚举ij，就是这道题的解法。

//lra233
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5010, INF = 0x3f3f3f3f;

int n, k;
LL b[N];
LL f[N][N];
LL q[N];
struct Seg
{
    int l, r;
    bool operator< (const Seg& t)
    {
        if (l == t.l) r > t.r;
        else return l < t.l;
    }
}s[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &s[i].l, &s[i].r);

    sort(s + 1, s + n + 1);
    int minn = s[n].r;
    int cnt = 0;
    for (int i = n - 1; i >= 1; i -- )
    {
        if (s[i].r >= minn)    //大区间 
        {
            b[ ++ cnt] = s[i].r - s[i].l;    
            s[i].l = INF;    //扔掉 
        }
        else
            minn = s[i].r;
    }
    memset(f, -INF, sizeof f);    //初始要设置为-INF,防止不合法状态 
    f[0][0] = 0;
    sort(s + 1, s + n + 1);
    n -= cnt;
    for (int j = 1; j <= k; j ++ )
    {
        int hh = 0, tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            while (hh <= tt && s[q[hh] + 1].r <= s[i].l) hh ++ ;
            if (hh <= tt) f[i][j] = -s[i].l + f[q[hh]][j - 1] + s[q[hh] + 1].r;
            while (hh <= tt && f[q[tt]][j - 1] + s[q[tt] + 1].r <= f[i][j - 1] + s[i + 1].r) tt -- ;
            q[ ++ tt] = i;    
        }
    }

    sort(b + 1, b + cnt + 1, greater<LL>());    
    LL ans = 0;
    for (int i = 2; i <= cnt; i ++ ) b[i] += b[i - 1];
    for (int i = 0; i <= min(k, cnt); i ++ )
        ans = max(ans, b[i] + f[n][k - i]);


    printf("%lld\n", ans);

    return 0;
}