考察点
LIS 变种: 要求找出最长子序列:(a1,b1),(a2,b2)…(an,bn)
该序列满足:an>…>a2>a1 且 bn>…>b2>b1
所以我们只需要先把 a从小到大排序,再对 b 找 LIS 即可
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5010;
struct node{
int a,b;
}pos[N];
int f[N];
int n;
bool cmp(node x,node y){
return x.a<y.a;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>pos[i].a>>pos[i].b;
sort(pos+1,pos+1+n,cmp);
f[1]=pos[1].b;
int l=1;
for(int i=2;i<=n;i++){
if(pos[i].b>f[l]) f[++l]=pos[i].b;
else {
int j=lower_bound(f+1,f+l+1,pos[i].b)-f;
f[j]=pos[i].b;
}
}
cout<<l;
return 0;
}