记录编号	577513	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022J]上升点列	最终得分	100
用户昵称	00000	是否通过	通过
代码语言	C++	运行时间	0.676 s
提交时间	2022-11-07 17:20:05	内存使用	2.79 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,ans;
int f[600][200];//f(i,j)：以i结尾，加j个点，最多连几个点 
struct node{
	int x,y;
}a[2000];
bool cmp(node j,node k)
{
	if(j.x!=k.x) return j.x<k.x;
	return j.y<k.y;
}
int dis(int j,int k)
{
	return a[j].x+a[j].y-a[k].x-a[k].y;
}
int main(){
	freopen("csp2022pj_point.in","r",stdin);
	freopen("csp2022pj_point.out","w",stdout);
cin>>n>>k;
for(int q=1;q<=n;q++) cin>>a[q].x>>a[q].y;
sort(a+1,a+n+1,cmp);
for(int q=1;q<=n;q++)
{
	for(int w=0;w<=k;w++)
	{
		f[q][w]=1;
		for(int e=1;e<q;e++)
		{
			if(a[e].x<=a[q].x&&a[e].y<=a[q].y)
			{
				if(w-dis(q,e)+1>=0)
				f[q][w]=max(f[q][w],f[e][w-dis(q,e)+1]+1);
			}
		}
	}
}
for(int q=1;q<=n;q++) ans=max(ans,f[q][k]);
cout<<ans+k;
return 0;
}