P8816 [CSP-J 2022] 上升点列（民间数据）

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[505][205],ans,c[505][505],rk,ri,rlt;
struct Node{
	int x, y;
}a[505];
bool cmp(Node p, Node q){
	if(p.x == q.x) return p.y < q.y;
	return p.x < q.x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		scanf("%d%d",&a[i].x, &a[i].y);
	}
	sort(a+1, a+n+1, cmp);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++){
			c[i][j] = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) - 1;
		}
	for(int i = 1; i <= n; i++)
		for(int k = 0; k <= m; k++) dp[i][k] = k+1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j < i; j++){
			for(int k = 0; k <= m; k++){//k = 0 开始 
				if(a[i].x >= a[j].x && a[i].y >= a[j].y && k >= c[i][j])
					dp[i][k] = max(dp[i][k], dp[j][k - c[i][j]] + c[i][j] + 1);
			}
		}
	}

	for(int i=1;i<=n;i++)
        ans=max(ans,dp[i][m]);
    cout<<ans;
	return 0;
}