问题1228--最多航线问题

1228: 最多航线问题

时间限制: 1 Sec  内存限制: 64 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

某国家被一条河划分为南北两部分，在南岸和北岸总共有n对城市，每对城市在对岸都有唯一的友好城市。任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往。于是他们向政府提出了申请。由于河面上终年有雾。政府决定允许开通的航线互不交叉（如果两条航线交叉，将有很大机会撞船）。
你的任务是编写一个程序来帮政府官员决定他们应拨款兴建哪些航线可以在安全条件下有最多航线可以开通。

输入

第一行两个由空格分隔的整数x，y，10≤x≤6000，10≤y≤100。x 表示河的长度而y表示宽。
第二行是一个整数n(1≤n≤5000)，表示分布在河两岸的城市对数。
接下来的n行，每行有两个由一个空格分隔的正数c，d（c、d≤x〉，描述每一对友好城市与河起点的距离，c表示北岸城市的距离，d表示南岸城市的距离。在河的同一边，任何两个城镇市的位置都是不同的。

输出

一行一个数，表示在安全条件下能够开通的最大航线数目

样例输入 Copy 

30 4
5
4 5
2 4
5 2
1 3
3 1

样例输出 Copy 

3

来源/分类

动态规划算法 
[提交] [状态]