AcWing 1012. 友好城市---二维数组排序(语法)
原题链接
简单
作者:
会飞的泡泡
,
2021-02-03 22:14:03
,
所有人可见
,
阅读 340
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=5010;
vector<vector<int> >a(maxn, vector<int>(2,0));
int n;
int dp[maxn];
int main(){
cin>>n;
for(int i=1 ;i<=n; i++){
cin>>a[i][0]>>a[i][1];
}
sort(a.begin()+1, a.begin()+n+1, []( auto p, auto q){
return p[0]<q[0];
});
int ans=-1;
for(int i=1; i<=n; i++){
dp[i]=1;
for(int j=1; j<i; j++){
if(a[j][1]<a[i][1]){
dp[i]=max(dp[i], dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}