本题要求是任意选两条不相交路径,我们可以按照其中一个序列坐标进行排序,排序之后我们对另一个序列求解最长上升子序列即可
证明算法:
设最优解中第一个序列的两座城市分别为x1和x2,其对应的友好城市分别为y1和y2,要使其不存在相交必须满足x1 < x2且y1 < y2
只要按照其中一个关键字排序便可构造出这样的序列
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 5010;
typedef pair<int,int> PII;
int n,ans;
PII a[N];
int f[N];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
f[i] = 1;
for(int j=1;j<i;j++){
if(a[j].y < a[i].y){
f[i] = max(f[i],f[j] + 1);
}
}
ans = max(ans,f[i]);
}
cout << ans;
return 0;
}