先排个序然后做最长上升子序列就行了。
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
struct Node{
int ll, ww;
}nd[50005];
int n, cnt, dp[5005];
bool cmp(Node x, Node y){
if(x.ll==y.ll) return x.ww>y.ww;
return x.ll>y.ll;
}
int main(){
cin>>n;
for(int i=1; i<=n; i++)
scanf("%d %d", &nd[i].ll, &nd[i].ww);
sort(nd+1, nd+1+n, cmp);
for(int i=1; i<=n; i++){
if(nd[i].ww>dp[cnt]) dp[++cnt] = nd[i].ww;
else *lower_bound(dp+1, dp+1+cnt, nd[i].ww) = nd[i].ww;
}
cout<<cnt<<endl;
return 0;
}