思路:
- 首先城市的坐标是按顺序排的,我们可以先将其中一岸(比如南岸)的城市排序;
- 排序后遍历南岸的城市,在所有合法的建桥方式中,南岸城市所对应的北岸友好城市的坐标一定是单调递增的。因为若不递增就说明出现了交叉航线,这个建桥方式就是不合法的;
- 使用找
最长上升子序列
的方法,求得航线的最多申请数。
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 5010;
int n;
PII q[N]; //数组中存南北岸城市的坐标
int f[N]; //f用来存最长上升子序列
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i)
cin >> q[i].first >> q[i].second;
sort(q, q + n); //对南岸城市排序
int res = 0;
for (int i = 0; i < n; ++ i) //求最长上升子序列
{
f[i] = 1;
for (int j = 0; j < i; ++ j)
if (q[i].second > q[j].second)
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}