[CSP-J 2022] 上升点列（DP）

题目传送门

解题思路

首先先讲这些点按照  从小到大排序。

然后，很容易想到设  表示到第  个点已经放了  个点的最长上升序列的长度。

所以，我们可以从前面的点转移（注意要判断一下  是否符合，因为我们只按照了  排序）；

于是，手推一下可以整出这样一个转移方程：

其中  是我们从前面转移的点的编号。

但是注意一下，我们取最大值时，要取 ，因为也要考虑在后面放  个点的情况。

时间复杂度 

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans;
struct node{
	int x,y;
}a[501];
bool cmp(node a,node b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int f[501][101];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=0;i<=m;i++)
		f[1][i]=i+1;
	
	for(int i=2;i<=n;i++)
	{	for(int j=0;j<=m;j++){
			for(int k=1;k<i;k++)
			{
				if(a[k].y>a[i].y)continue;
				if(a[k].x==a[i].x&&a[i].y-a[k].y==1||a[k].y==a[i].y&&a[i].x-a[k].x==1)
					f[i][j]=max(f[i][j],f[k][j]);
				else{
					int temp=a[i].x-a[k].x+a[i].y-a[k].y-1;
					if(temp<=j)
					{
						f[i][j]=max(f[i][j],f[k][j-temp]+temp);
					}
				}
			}
			f[i][j]++;
			ans=max(ans,f[i][j]+m-j);}
	}
	cout<<ans;
	return 0;
}