[2017 CCPC-Final][HDU 6249] Alice’s Stamps

    题意：给出n段区间，范围在\([1...m]\)内，选出最多k段，问最多能覆盖多少个点。(\(n,m,k<=2000\))

    题解：如果一个区间被另一个区间包含，那么这个区间显然没有另一个优，直接扔掉就好了。给区间按左端点排序，设\(f[i][j]\)表示前i个点，选出j段区间最多能覆盖多少个点，转移就用覆盖当前点的左端点最小的区间来更新。

    真的不明白考试的时候为什么会想成单调队列然后改成单调栈然后改成双端队列......

#include <bits/stdc++.h>
using namespace std;
const int maxn=2010;

void read(int &x)
{
    char ch;
    while ((ch=getchar())<'0' || ch>'9');
    x=ch-'0';
    while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';
}

struct Set
{
    int l,r;
    bool operator< (const Set &b) const {return l<b.l || (l==b.l && r<b.r);}
}S[maxn];

int f[maxn][maxn];
int n,m,k;

void DP()
{
    memset(f[0],0,sizeof(f[0]));
    for (int i=1,j=1;i<=n;i++)
    {
        for (int k0=1;k0<=min(i,k);k0++)
        {
            f[i][k0]=max(f[i-1][k0],f[i][k0-1]);
			while (j<=m && S[j].r<i) j++;
            if (j>m || S[j].l>i) continue;
            int res=f[S[j].l-1][k0-1]+i-S[j].l+1;
            if (res>f[i][k0]) f[i][k0]=res;
        }
    }
}

int main()
{
    int T;
    read(T);
    for (int t=1;t<=T;t++)
    {
        printf("Case #%d: ",t);
        read(n),read(m),read(k);
        for (int i=1;i<=m;i++) read(S[i].l),read(S[i].r);
        sort(S+1,S+1+m);
		for (int i=1,j=1,m0=m;i<=m0;i++) if (S[i].l!=S[i+1].l || i==n)
			S[m=j++]=S[i];
        DP();
        int ans=0;
        for (int i=1;i<=k;i++) ans=max(ans,f[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}