loj 1017(dp)

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25843

思路：我们可以发现题目与点的X坐标没有关系，于是可以直接对y坐标进行排序，然后进行dp,dp[i][j]表示以j个区间覆盖前i个点的最大覆盖数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
#define FILL(a,b) memset(a,b,sizeof(a))

int n,w,k,dp[MAXN][MAXN];
int y[MAXN];
int pre[MAXN],num[MAXN];

int main()
{
    int _case,x,t=1;
    scanf("%d",&_case);
    while(_case--){
        scanf("%d%d%d",&n,&w,&k);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y[i]);
        }
        sort(y+1,y+1+n);
        FILL(dp,0);
        int p1=1,p2=1;
        pre[1]=0,num[1]=1;
        while(p1<=n){
            p1++;
            while(y[p1]-y[p2]>w)p2++;
            pre[p1]=p2-1;
            num[p1]=p1-p2+1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=max(dp[i-1][j],dp[pre[i]][j-1]+num[i]);
            }
        }
        printf("Case %d: %d
",t++,dp[n][k]);
    }
    return 0;
}