题目描述
blablabla
样例
blablabla
算法1
(动态规划)
时间复杂度
$o(n^2)$
参考文献
C++ 代码(结构体版)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int n,f[N];
struct note{
int x;
int y;
}city[N];
inline int read(){
int f=1,x=0; char ch;
do{ch=getchar();if(ch=='-')f=-1;} while(ch<'0'||ch>'9');
do{x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} while(ch>='0'&&ch<='9');
return f*x;
}
bool cmp(note a,note b){
return a.x>b.x;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
city[i].x=read();
city[i].y=read();
}
sort(city+1,city+n+1,cmp);
for(int i=n;i;i--){
f[i]=1;
for(int j=n;j>i;j--){
if(city[i].y>city[j].y)
f[i]=max(f[i],f[j]+1);
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
cout << ans << endl;
return 0;
}