题解

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
};
node d[505];
bool cmp(node a,node b){
	if(a.x!=b.x) return a.x < b.x;
	else return a.y<b.y;
}
int ds(int i,int h){
	return (d[i].x-d[h].x)+abs(d[i].y-d[h].y);
}
int main(){
	int n,k;
	cin >> n >> k;

	for(int i=1;i<=n;i++){
		cin >> d[i].x >> d[i].y;
	} 
	sort(d,d+n+1,cmp);
	
	int dp[505][105]={0};
	for(int j=0;j<=k;j++){
		dp[1][j] = j+1;
	}
	for(int i=2;i<=n;i++){
		for(int j=0;j<=k;j++){
			for(int h=1;h<i;h++){
				if(d[i].x>=d[h].x&&d[i].y>=d[h].y){
					int jl = ds(i,h);
					if(jl==1){
						dp[i][j] = max(dp[h][j]+1,dp[i][j]);
					}else if(jl<=j+1){
						dp[i][j] = max(dp[i][j],max(1+j,dp[h][j-jl+1]+(jl-1)+1));
					}else{
						dp[i][j] = max(1+j,dp[i][j]);
					}
				}else{
					dp[i][j] = max(1+j,dp[i][j]);
				}
				
			}
		}
	} 
	int rs = 0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=k;j++){
			rs = max(rs,dp[i][j]);
		}
	}
	cout << rs;
	return 0;
}