摘要：
某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有一个城市作为友好城市。每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。政府决定允许开通的航线就互不交叉。兴建哪些航线以使在安全条件下有最多航线可以被开通。
某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有一个城市作为友好城市。每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。政府决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。兴建哪些航线以使在安全条件下有最多航线可以被开通。
Input Format：
第一行两个由空格分隔的整数x，y，10〈=x,y〈=60000，x,y中较长的表示河的长度另一个表示宽。第二行是一个整数N(1<=N<=5000)（P.S.：X,Y没有任何用处），表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。
30 4
5
4 5
2 4
5 2
1 3
3 1
Sample Output：
一个整数，表示安全条件下能够开通的最大航线数目。
3
思路：
既然要看是避开交集不让你先按C或D排一下序。这样在一个有序的队列就就好搞了。
如果a,b不相交，自然先后先后顺序是一样的。用for循环找最多的次数。
然后，用F【？？】数组记录大小。
cpp：
1 #include <cstdio> 2 #include <algorithm> 3 using namespacestd; 4 5 intx,y,n,i,j; 6 int f[5000]; 7 structCity{ 8 intc,d; 9 }city[5000]; 10 11 int cmp(const City &a,const City &b) 12 { 13 if (a.c<b.c) return 1; 14 else return 0; 15 } 16 17 intmain() 18 { 19 /*freopen("ship.in","r",stdin); 20 freopen("ship.out","w",stdout); */ 21 scanf("%d%d",&x,&y); 22 scanf("%d",&n); 23 for (i=0; i<n; i++) scanf("%d%d",&city[i].c,&city[i].d); 24 sort(city,city+n,cmp); 25 int max=1; 26 for (i=0;i<n;i++) 27 { 28 f[i]=1; 29 for (j=0;j<i;j++) 30 if (city[j].d<city[i].d && f[j]+1>f[i]) f[i]=f[j]+1; 31 if (f[i]>max) max=f[i]; 32 } 33 printf("%d ",max); 34 return 0； 35 }