题解

有点东西，写发题解。

我们知道，在本题中，要一次走完，行只能单调递增。
在同一行中，列也只能单调递增。

也就是说，选择了 { x , y } 这个点，之后的 x 都不能回头，y在同一行中同理。

于是转换成求最长不下降（往上）的最小个数。

根据 Dilworth 定理，求最长下降子序列的长度即可。

AC CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;
int n,m,p,l,dp[N];
struct Node{
	int x,y;
}a[N];

bool cmp(Node x,Node y)
{
	return (x.x==y.x?x.y<y.y:x.x<y.x);
}

signed main()
{
	scanf("%lld%lld%lld",&n,&m,&p);
	for(int i=1;i<=p;++i)
	{
		scanf("%lld%lld",&a[i].x,&a[i].y);
	}
	sort(a+1,a+p+1,cmp);
	dp[++l]=a[1].y; 
	for(int i=2;i<=p;++i)
	{
		if(a[i].y<dp[l])
		{
			dp[++l]=a[i].y;
		}
		else
		{
			int upd=lower_bound(dp+1,dp+l+1,a[i].y,greater<int>() )-dp;
			dp[upd]=a[i].y;
		}
	}
	printf("%lld",l);
	return 0;
}