2022 CSP-J 上升序列

/*
对于当前的n个点排序按照x然后y，从小到大
f[i][j]以当前第i个点作为结尾，还剩下j个自由点
max(f[i][j]+j);
当前的这个点为最后一个，还剩下j个直接拼接后面
枚举合法状态下的第k个点(坐标不超过i),假设d为距离
中间使用d-1个自由点
f[i][j]=max(f[k][j+d-1]+d);
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int,int>a[505];
int f[505][505];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){//输入每一个点的坐标 
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=1;i<=n;i++){//枚举结尾点是第几个点 
		for(int j=0;j<=m;j++){//枚举剩下数量 
			f[i][j]=1;
			for(int k=1;k<i;k++){//枚举结尾点前面的一个点计算转移 
				if(a[i].second>=a[k].second){
					//计算两点之间的距离 
					int d=a[i].first-a[k].first+
						  a[i].second-a[k].second; 
					int t=j+d-1;
					if(t<=m){//如果当前需要d个自由点没有超出总数 
						f[i][j]=max(f[i][j],f[k][t]+d); 
					} 
				}
			}
			ans=max(ans,f[i][j]+j);
		}
	} 
	cout<<ans<<endl;
	return 0;
}