题意：给出许多连线，要你删除一些使得剩下的连线最多且不想交，抽象出来就是最长上升序列问题（LIS）

LIS有两种经典解法，一种是DPO（N^2)的时间复杂度，还有一种二分O（NlogN）的时间复杂度。

第一种方法：

推荐题目PKOJ2533 ――Longest Ordered Subsequence 裸LIS

#include 
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #define N 2222//最长上升子序列，n^2算法 using namespace std; int dp[N]; int a[N]; int main() { int n; while(~scanf("%d",&n)) { memset(dp,0,sizeof dp); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[1]=1;int ans=1; for(int i=2;i<=n;i++) { int m=0; for(int j=1;j
       
        m&&a[i]>a[j]) m=dp[j]; } dp[i]=m+1; if(ans
        
         
 
         第二种方法：
         
 
         
POJ1631，给的数据40000，直接做的话会超时，所以要用二分来做
 
         
http://www.docin.com/p-540470161.html 豆丁上把这种方法讲解的很好的一个PPT，看了就懂
 
 
         

         
#include 
          
           
#include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define N 45000 using namespace std; int a[N]; int ans[N];//注意，ans数组储存的不是LIS，而是对应长度LIS的最小末尾 int len; int binary_search(int i) { int le,ri,mid; le=0;ri=len; while(le
                
                 =a[i]) ri=mid; else le=mid+1; } return le; } int main() { int n; int p; while(~scanf("%d",&n)) { while(n--) { scanf("%d",&p); for(int i=1;i<=p;i++) scanf("%d",&a[i]); ans[1]=a[1]; len=1; for(int i=1;i<=p;i++) { if(ans[len]
                 
                  
 有关的题目推荐：POJ 1887 POJ 1609