HDU 1950 Bridging signals (DP) - c++编程基础

题目地址：HDU 1950

这题是求最长上升序列，但是普通的最长上升序列求法时间复杂度是O(n*n)，显然会超时。于是便学了一种O(n*logn)的方法。也很好理解。感觉还用到了一点贪心的思想。

具体的见这篇博客吧，写的很通俗易懂。传送门

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL long long int a[50000], b[50000], len; int bin_seach(int x) { int low=1, high=len, mid, ans; while(low<=high) { mid=low+high>>1; if(b[mid]>=x) {high=mid-1;ans=mid;} else low=mid+1; } return ans; } int main() { int t, n, i, pos; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i
             
              b[len]) { b[++len]=a[i]; } else { pos=bin_seach(a[i]); b[pos]=a[i]; } } printf("%d\n",len); } return 0; }