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;
}