友好城市

友好城市
题目概述：有n个城市分布在一条大河两岸，现在，两岸的城市准备在河上修建桥。每个城市在河对岸都有自己的友好城市，只有友好城市之间才能建立桥。问最多可以修建多少座桥，且桥与桥之间互不交叉。
解题思路：我们可以先考虑怎样会出现交叉情况，当一侧的城市编号为正序(3,4)，另一侧的城市编号出现倒序(6,5)，那么就会出现交叉情况。我们可以先保持一侧有序，再尽可能保证另一侧有序即可，即求解最长上升子序列。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
const int N = 5010;

PII cities[N];
int f[N];

void solve(){
	int n;
	cin >> n;

	for(int i = 0; i < n; i ++){
		int a,b;
		cin >> a >> b;
		cities[i] = {a,b};
	}

	sort(cities,cities + n);
	for(int i = 0; i < n; i ++){
		f[i] = 1;
		for(int j = 0; j < i; j ++){
			if(cities[j].second < cities[i].second)
				f[i] = max(f[i],f[j] + 1);
		}
	}

	int res = 0;
	for(int i = 0; i < n; i ++)res = max(res,f[i]);

	cout << res << endl;
}

int main(){
	int T = 1;

	while(T --){
		solve();
	}
	
}