题目大意

在一个二维平面内，给定 n 个整数点 (xi, yi)(xi​,yi​)，此外你还可以自由添加 k 个整数点。

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

思路

先把点进行排序，然后从第i个枚举到第k个再列出状态转移方程

代码

#include<bits/stdc++.h>
using namespace std;
int k,n;
struct node{
	int x,y;
	bool operator<(const node &w) const{
	    if(x==w.x) return y<w.y;
	    return x<w.x;
	}
}a[1111];
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);
	for(int i=1;i<=n;i++){
		f[i][k]=1;
		for(int j=0;j<=k;j++){
			for(int l=1;l<i;l++){
				if(a[l].x>a[i].x||a[l].y>a[i].y){
					continue;//已经试过直接舍去
				}
				int dx=abs(a[i].x-a[l].x);//两个横坐标的差
				int dy=abs(a[i].y-a[l].y);//两个纵坐标的差
				int d=dx+dy-1;//减去一个重复的点2
				if(j+d>k){
					continue;//要添加的点数超过了k舍去
				}
				f[i][j]=max(f[i][j],f[l][j+d]+d+1);
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			sum=max(sum,j+f[i][j]);//对比得最大长度
		}
	}
	cout<<sum;
	return 0;
}

思想感情

*😕 *