凌艺樽 • 1个月前
有点东西,写发题解。
我们知道,在本题中,要一次走完,行只能单调递增。
在同一行中,列也只能单调递增。
也就是说,选择了 { x , y } 这个点,之后的 x 都不能回头,y在同一行中同理。
于是转换成求最长不下降(往上)的最小个数。
根据 Dilworth 定理,求最长下降子序列的长度即可。
#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;
}
评论: