AcWing 1012. 友好城市
原题链接
简单
作者:
徐学神
,
2023-02-06 13:09:14
,
所有人可见
,
阅读 97
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e3+10;
struct node {
ll sth,nth;
}a[N];
ll n,dp[N],ans;
bool cmp(node x,node y) {
if(x.sth==y.sth) return x.nth<=y.nth;
return x.sth<y.sth;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i].sth>>a[i].nth;
sort(a+1,a+n+1,cmp);
for(ll i=1;i<=n;i++) {
dp[i]=1;
for(ll j=1;j<i;j++) {
if(a[i].nth>a[j].nth) dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}