友好城市

问题描述

Palmia国有一条横贯东西的大河，河的南北两岸上有位置各不相同的N个城市。北岸每个城市有且仅有一个对应的友好城市在南岸，而且每对城市的友好关系都是独一无二的。每对友好城市都向政府申请在河上建立一条直线航道以连接两城。但是，由于大雾，政府决定避免任意两条航道交叉，以防发生事故。编写程序帮助政府在保证航线不相交的前提下，尽可能多地批准申请。

输入格式

第1行：一个整数N（1<=N<=5000），表示城市数量。 第2行到第n+1行：每行两个整数，用空格分隔，表示南岸和北岸的每对友好城市的坐标（0<=xi<=10000）。

输出格式

输出一个整数，表示政府所能批准的最多申请数。

输入样例

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例

4

解题思路

理解题目的关键是避免航道交叉。首先，将南岸城市按坐标排序：

由于南岸城市已经排好序，如果北岸城市不形成一个递增序列的话，航道就会交叉。因此，问题可以转化为寻找北岸城市的最长不下降子序列。