题目

在一个二维平面内，给定n个整数点 (Xi,Xi)，此外你还可以自由添加k个整数点。你在自由添加k个点后，还需要从n+k个点中选出若干个整数点并组成一个序列，使 得序列中任意相邻两点间的欧几里得距离恰好为1而且横坐标、纵坐标值均单调不减，求出满足条件的序列的最大长度。

1≤n≤500，0≤k≤100。对于所有给定的整点，其横纵坐标1≤xi,yi≤10^9

思路

排序，枚举，最后得出状态转移方程

代码

#include<cmath>
#include<algorithm>
using namespace std;
int n,k;
struct node{
	int x,y;
}a[501];
bool cmp(node i,node k){
	if(i.x==k.x) return i.y<k.y;
	return i.x<k.x;
}
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+1+n,cmp);
	for(int i=1;i<=n;i++){
		f[i][k]=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 d=abs(a[i].x-a[t].x)+abs(a[i].y-a[t].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;
}

题解入口：题解 - 「CSP-J 2022」上升点列（point） - TeMenHu (temege.com)