hdu 1950 最长上升子序列

动态规划 LIS nlogn 做法 采用而二分来优化

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ;10 11 const int maxn = 40011 ;12 int a[maxn],ans[maxn] ;13 int n,t,len,pos ;14 15 int main() 16 {17 scanf("%d",&t) ;18 while(t--) 19 {20 scanf("%d",&n) ;21 for(int i=1;i<=n;i++) 22 scanf("%d",&a[ i ]) ;23 len = 1 ;24 ans[ 1 ] = a[ 1 ] ;25 for(int i=2;i<=n;i++) 26 if(a[i]>ans[len]) ans[++len] = a[ i ] ;27 else28 {29 pos = lower_bound( ans+1,ans+len+1-1,a[ i ] ) - ans ; //30 //pos = lower_bound( ans,ans+len,a[ i ] ) - ans ; 31 ans[ pos ] = a[ i ] ;32 }33 printf("%d\n",len ) ; 34 }35 return 0 ;36 }