1.5　和谐俱乐部

【题目描述】 和谐俱乐部（beautiful）SGU 199

某个私人俱乐部有N个会员，每一个会员都是既美丽又强壮的（以A代表强壮值，以B代表美丽值），但他们都有一个缺点，就是爱嫉妒。例如i会员嫉妒j会员的条件是：A_i≤A_j并且B_i≥B_j，A_i≥A_j并且B_i≤B_j。但是如果j会员的美丽值和强壮值都不如i会员，则i会员会忽视j会员的存在；而如果j会员的美丽值和强壮值都高于i会员，则i会员会非常尊敬j会员。

俱乐部经理准备组织一次舞会，但是他担心各会员之间会因为嫉妒而引发争斗。所以，邀请哪些会员前来参加舞会实在是让经理伤脑筋。那么，精通计算机编程的你，能告诉经理该给哪些会员发送邀请函及邀请的人数最多是多少吗？

【输入格式】

第一行为整数N（2≤N≤100 000），代表N个会员。剩下N行为每个会员的A值和B值（1≤A_i，B_i≤109）。

【输出格式】

输出最多邀请人数。

【输入样例】

4

3 2

2 1

5 5

1 2

【输出样例】

3

【算法分析】

这是一道求最长不下降子序列的题，但略微有些难度，关键是有两个序列，即A和B，我们可以先对A序列进行由小到大的排序，B序列会随A序列的变动而变动。

假设输入样例如下：

4

3 2

2 1

5 5

1 2

定义一个二维数组a[5][N]，数组内容如表1.6所示。

表1.6

对A值进行不下降排序，排序的同时，序号与B值也会随之变动，如表1.7所示。

表1.7

现在问题转化为求B序列的最长不下降子序列的问题了。