首先我们定义好结构体,把输入的点以x为第一关键字,y为第二关键字进行排序

struct node{
	int x,y;
	bool operator< (const node &w) const
	{
		if(x==w.x)	return y<w.y;
		return x<w.x;
	}
}a[501];

设f[i][j]为枚举到第i个点,还有j个自由点时序列最大长度,则状态转移方程为

f[i][j]=max(f[i][j],f[t][j+d+1]

t是从1到i-1,d是第i个点和第t个点之间要添加的自由点个数 求完所有序列的长度后,再找出最大长度就做完了

代码

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,k;
struct node{
	int x,y;
	bool operator< (const node &w) const
	{
		if(x==w.x)	return y<w.y;
		return x<w.x;
	}
}a[501];
int f[501][101];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        f[i][k]=1;//初始没用自由点的值为1
        for(int j=0;j<=k;j++){
            for(int t=1;t<i;t++){
                if(a[t].x>a[i].x||a[t].y>a[i].y)	continue;//不符合题意跳过
                int x=abs(a[i].x-a[t].x);
                int y=abs(a[i].y-a[t].y);
                int d=x+y-1;//要加多少个自由点
                if(j+d>k){//自由点不够
                    continue;
                }
                f[i][j]=max(f[i][j],f[t][j+d]+d+1);
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            ans=max(ans,j+f[i][j]);
        }
    }
    cout<<ans;
    return 0;
}