地址：

题意：上面n个点，下面n个点，然后在这2n个点之间随意连线，一个点只能被连一次，问最多有多少条线不交叉。

mark：把上面点排序后，那么就转换成最大升序子序列的问题了。可以看看我上一篇博客~poj 3903

代码：

#include 
     
      #include 
      
       #include 
       
        typedef struct{    int s,e;}city;city c[500010];int len;int d[500010];int cmp(const void *a, const void *b){    return (*(city *)a).s - (*(city *)b).s;}int find(int m){    int fr = 0, la = len-1, mid;    while(fr <= la)    {        mid = (fr+la)/2;        if(d[mid] == m) return 0;        if(d[mid] > m) la = mid-1;        else fr = mid+1;    }    return fr;}int main(){    int n,m;    int i,j;    j = 1;    while(~scanf("%d", &n))    {        len = 0;        for(i = 0; i < n; i++)            scanf("%d %d", &c[i].s, &c[i].e);           qsort(c, n, sizeof(c[0]), cmp);        for(i = 0; i < n; i++)        {            if(!len) {d[len++] = c[i].e; continue;}            if(c[i].e < d[0]) {d[0] = c[i].e; continue;}            if(c[i].e > d[len-1]) {d[len++] = c[i].e; continue;}            m = find(c[i].e);            if(m) d[m] = c[i].e;        }        printf("Case %d:\nMy king, at most %d road", j++, len);        if(len-1) putchar('s');        puts(" can be built.\n");    }    return 0;}