题目链接: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=;
scanf("%d",&_case);
while(_case--){
scanf("%d%d%d",&n,&w,&k);
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y[i]);
}
sort(y+,y++n);
FILL(dp,);
int p1=,p2=;
pre[]=,num[]=;
while(p1<=n){
p1++;
while(y[p1]-y[p2]>w)p2++;
pre[p1]=p2-;
num[p1]=p1-p2+;
}
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
dp[i][j]=max(dp[i-][j],dp[pre[i]][j-]+num[i]);
}
}
printf("Case %d: %d\n",t++,dp[n][k]);
}
return ;
}