P8816

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , k;
int dp[505][505];
struct Point {
	int x;
	int y;
};
Point point[505];

inline bool cmp(Point a , Point b) {
	if(a.x != b.x)
		return a.x < b.x;
	else
		return a.y < b.y;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= n;i ++)
		cin >> point[i].x >> point[i].y;
	sort(point + 1 , point + 1 + n , cmp);
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= k;j ++)
			dp[i][j] = j + 1;
	for(int i = 2;i <= n;i ++) {
		for(int j = 1;j < i;j ++)  {
			if(point[i].y < point[j].y)
				continue;
			int dis = point[i].x - point[j].x + point[i].y - point[j].y + 1;
			for(int x = 0;x <= k;x ++)
				dp[i][x] = max(dp[i][x] , dp[j][x - dis] + dis + 1);
		}
	}
//	cout << '\n';
	int maxn = 0;
//	for(int i = 1;i <= n;i ++)
//		cout << point[i].x << " " << point[i].y << '\n';
//	cout << '\n';
//	for(int i = 1;i <= n;i ++) {
//		for(int j = 1;j <= k;j ++)
//			cout << dp[i][j] << " ";
//		cout << '\n';
//	}
	for(int i = 1;i <= n;i ++)
		maxn = max(maxn , dp[i][k]);
	cout << maxn << '\n';
	return 0;
}