观察一下题意，很容易发现和LIS有很大的关系，所以直接考虑dp。但是LIS只是一维的，这是个坐标系上的，所以需要转换一下。

首先我们设 f(i,j) 为在前 i 个点中 ， 还剩 j 个自由点时连续上升点列的最大值。此时我想想该怎么转移，因为要用到自由点，所以我们考虑通过前面的与该点保持单调上升的点的状态转移。再考虑回LIS的模板部分：

for(int i=1;i<=n;i++){
	f[i]=1;
	for(int z=1;z<i;z++){
		if(a[z]<a[i]){
			f[i]=max(f[i],f[z]+1);
		}
	}
}

是不是感觉有点感觉了（

然后我们只需要再加入一重循环枚举可以使用的自由点个数 ， 然后判断第 z 个点和第 i 个点是否满足单调性 ， 不满足要跳过该点。接着计算第 z 个点和第 i 个点之间需要增加的自由点，计为 d , 然后判断没有使用的自由点（即 j），和还要加上的自由点 d ， 的和是否超过 最多可以加上的点 k ， 超过就要跳掉。如果还满足那么就可以转移了，状态转移方程就是

f( i , j ) = max{ f( i , j ) , f( z , j + d) + d + 1}

d = |i.x - z.x| + | i.y - i.z| - 1

ps:| x | 的意思是 x 的绝对值

解释一下为什么：首先考虑一下 f( z , j + d) + d + 1 的意义是什么，是不是就是“还剩 j+d 个自由点 再加上到 点 i 的自由点个数加1”

那么为什么要 + 1 呢？ 因为 d 是没有算上点 i 需要再加上去

还要注意输入后要先排序一边，不然会转移不了。

注意最后计算答案的时候我们需要再重新遍历一次整个 f 数组 ， 并且将每个状态上剩余的 j 也加上。因为我们之前转移定义的就是还剩下 j 个自由点的，所以我们要再加上 不然就会寄！

那么

OK

上代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int f[N][110];
struct node{
	int x,y;
	
}a[N];
int n,k;
inline bool cmp(node a,node b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
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,cmp);
	
	for(int i=1;i<=n;i++){
		f[i][k] = 1;
		for(int j=0;j<=k;j++){
			
			for(int z=1;z<i;z++){
				if(a[i].x < a[z].x || a[i].y < a[z].y) continue; // 维护单调递减 
				int d = abs(a[i].x - a[z].x) + abs(a[i].y - a[z].y) - 1;// i 和 z 之间要加的自由点个数
				 
				if(j + d > k) continue;
				f[i][j] = max(f[i][j] , f[z][j + d] + d + 1); 
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++)
			ans = max(ans , f[i][j] + j);
	}
	cout << ans ;
	return 0;
}