G League of Legends

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

对一列区间的 dp 问题。将包含关系的区间排除后就会变成 $l_i$ 与 $r_i$ 都递增的一系列区间，这样会明显好 dp 很多。无论是小包含大还是大包含小。

将问题简化之后根据简单的贪心思想得到所有的组都是相邻的，就可以用单调队列优化 dp。

我好久没打单调队列了于是有很多细节或多或少都出了问题... 包括有很多地方其实是不需要进行特殊情况判断的。

哎。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> mpair;
const int N=5e3+1;
typedef long long ll;
ll f[N][N];
struct Pair {
    int l, r;
} ;
Pair pa[N], pb[N];
int pc[N];
int ppb, ppc;
bool cmp(const Pair &a, const Pair &b) {
    return a.l==b.l?a.r<b.r:a.l<b.l;
}
bool cmp2(const int &a, const int &b) {
    return a>b;
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d%d", &pa[i].l, &pa[i].r), pa[i].r--;
    sort(pa+1, pa+1+n, cmp);
    for(int i=1; i<=n; i++) {
        while(ppb && pa[i].r<=pb[ppb].r) {
            pc[ppc++]=pb[ppb].r-pb[ppb].l+1;
            ppb--;
        }
        pb[++ppb]=pa[i];
    }
    sort(pc, pc+ppc, cmp2);
    memset(f, -0x3f, sizeof(f));
    f[0][0]=0;
    int mfq[N], mfr[N], head, tail;
    for(int j=1; j<=k; j++) {
        head=tail=0;
        for(int i=0; i<=ppb; i++) {
            while(head!=tail && pb[i].l>mfr[head]) head++;
            if(head!=tail) f[i][j]=mfq[head]-pb[i].l+1;
            while(head!=tail && f[i][j-1]+pb[i+1].r>=mfq[tail-1])
                tail--;
            mfq[tail]=f[i][j-1]+pb[i+1].r;
            mfr[tail++]=pb[i+1].r;
        }
    }
    ll rua=0, ans=f[ppb][k];
    for(int i=0; i<ppc; i++) {
        rua+=pc[i];
        ans=max(ans, f[ppb][k-i-1]+rua);
    }
    printf("%lld\n", max(ans, 0ll));
    return 0;
}