hdu 1950 最长上升子序列
动态规划 LIS nlogn 做法 采用而二分来优化
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <algorithm> 7 #include <iomanip> 8 #include <iostream> 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 else 28 { 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 ",len ) ; 34 } 35 return 0 ; 36 }