1263:友好城市
1263:友好城市
- 北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同
- 在保证任意两条航线不相交的情况下，被批准的申请尽量多
题目分析：
如图：最开始所有点为图1这种情况，我们需要处理不相交 - 那么转换为图2，需要先把第一列数从小到大排列
- 为了求得最多的情况，求第二列数的最长上升子序列（保证这列坐标从小到大，这样就不相交）
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define mm(a,x) memset(a,x,sizeof a)
#define mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
const int N = 5010;
int n;
pii q[N];
int f[N];
int main() {
cin >> n;
for(int i = 1; i <= n; i ++ ){
cin >> q[i].first >> q[i].second;
}
sort(q + 1,q + n + 1);
int res = 0;
for(int i = 1; i <= n; i ++ ){
f[i] = 1;
for(int j = 1; j < i; j ++ ){
if(q[j].second < q[i].second){
f[i] = max(f[i],f[j] + 1);
}
}
res = max(res,f[i]);
}
cout<<res;
return 0;
}
美的集团公司福利 798人发布