算法1

(二分LIS) $O(n^2)$

时间复杂度

o(nlogn)

算法

首先对其中一边的城市排序，然后找对面城市的最长上升子序列就行了

JAVA 代码

import java.util.Arrays;
import java.util.Scanner;
class hl implements Comparable<hl>
{
    int a,b;
    public hl(int a,int b)
    {
        this.a=a;
        this.b=b;
    }
    @Override
    public int compareTo(hl o) {
        return Integer.compare(this.a, o.a);
    }
}
public class Main {
    static int n;
    static hl arr[]=new hl[5010];
    static int dp[]=new int[5010];
    static int getLIS()
    {
        int cnt=0;
        dp[cnt++]=arr[1].b;
        for(int i=2;i<=n;i++)
        {
            if(arr[i].b>dp[cnt-1])
            {
                dp[cnt++]=arr[i].b;
            }
            if(arr[i].b<dp[cnt-1])
            {
                //find the min which is bigger than dp[i]
                int l=0,r=cnt-1;
                while(l<r)
                {
                    int mid=l+r>>1;
                    if(dp[mid]>=arr[i].b)
                    {
                        r=mid;
                    }else {
                        l=mid+1;
                    }
                }
                dp[r]=arr[i].b;
            }
        }
        return cnt;
    }
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            arr[i]=new hl(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(arr,1,n+1);
        System.out.println(getLIS());
    }
}