算法分析

• 条件一：每个城市只能建立一座桥

• 条件二：所有的桥与桥之间不能相交

• 目标：最多能建立多少座桥

步骤

• 1、通过排序，固定自变量的顺序

• 2、找因变量的最大上升子序列
  

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 5010;
    static PIIs[] city = new PIIs[N];
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        for(int i = 1;i <= n;i++)
        {
            String[] s1 = reader.readLine().split(" ");
            int first = Integer.parseInt(s1[0]);
            int second = Integer.parseInt(s1[1]);
            city[i] = new PIIs(first,second);
        }
        Arrays.sort(city,1,n + 1);
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            f[i] = 1;
            for(int j = 1;j < i;j++)
            {
                if(city[j].getFirst() < city[i].getFirst())
                    f[i] = Math.max(f[i],f[j] + 1);
            }
            res = Math.max(res, f[i]);
        }
        System.out.println(res);


    }
}
class PIIs implements Comparable<PIIs>{

    private int first;
    private int second;
    public int getFirst()
    {
        return this.first;
    }
    public int getSecond()
    {
        return this.second;
    }
    public PIIs (int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(this.second, o.second);
    }

}

c ++代码($O(nlogn)$)

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII city[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0;i < n;i ++) scanf("%d%d", &city[i].first, &city[i].second);
    sort(city, city + n);

    int len = 0;
    for(int i = 0;i < n;i ++)
    {
        int l = 0,r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < city[i].second) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = city[i].second;
        len = max(len, l + 1);
    }
    printf("%d\n", len);

    return 0;
}