记录编号 577436 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 [CSP 2022J]上升点列 最终得分 100
用户昵称 Gravatar在大街上倒立游泳 是否通过 通过
代码语言 C++ 运行时间 0.217 s
提交时间 2022-11-03 13:19:09 内存使用 2.45 MiB
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,k;
int f[505][200];
int ans;
struct point{
	int x,y;
}tu[505];
/*bool zai(point dian)
{
	for(int i=1;i<=n;i++)
	{
		if(dian.x==tu[i].x&&dian.y==tu[i].y) return true;
	}
	return false;
}
void dfs(point dian,int ke,long long xian)
{
	ans=max(xian,ans);
	point xin;
	xin=dian;
	xin.x+=1;
	if(zai(xin)) dfs(xin,ke,xian+1);
	else if(ke>0) dfs(xin,ke-1,xian+1);
	xin.x-=1;
	xin.y+=1;
	if(zai(xin)) dfs(xin,ke,xian+1);
	else if(ke>0) dfs(xin,ke-1,xian+1);
}*/
bool cmp(point a,point b)
{
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
 } 
int main()
{
	freopen("csp2022pj_point.in","r",stdin);
	freopen("csp2022pj_point.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++) 
	{
		cin>>tu[i].x>>tu[i].y;
	}
	sort(tu+1,tu+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i][0]=1;
		for(int j=1;j<i;j++)
		{

			if(tu[i].y<tu[j].y) continue;
			int dis=tu[i].y-tu[j].y+tu[i].x-tu[j].x-1;
			for(int l=0;l<=k;l++)
			{
				if(l+dis>k) continue;
				f[i][l+dis]=max(f[i][l+dis],f[j][l]+dis+1);
				ans=max(ans,f[i][l+dis]+k-l-dis);
			}
		}
	}
	cout<<ans;
    return 0;
}