/*
bupt 1032
nlogn LIS
注意!
是最長(zhǎng)不減序列(*1),而非最長(zhǎng)升序列(*2)
則當(dāng)t>=D[len]就直接更新len+1
而t<D[len]時(shí),應(yīng)在D[1..len]中查找最大的j,滿足D[j]<=A[t](在*2中,是滿足D[j]<A[t]),
將t接在D[j]后得到更長(zhǎng)的不減序列,同時(shí)更新D[j+1]=t
這是我WA很多次的地方.對(duì)這個(gè)算法未理解透徹
附一組原先錯(cuò)誤程序WA的數(shù)據(jù):
40
9 7 10 13 18 4 13 37 24 7 30 17 36 20 23 26 35 16 7 25 7 30 39 3 9 11 14 8 29 35 35 17 6 11 25 25 21 17 32 38
答案12
*/
#include <iostream>
using namespace std;
int T,N,m,cnt,r[50010];
int main(){
int i,j,k;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
cnt=0; r[0]=-1;
for(i=1;i<=N;i++){
scanf("%d",&m);
if(m>=r[cnt]){ //not '>'
r[++cnt]=m;
}
else{
int bl=1,bh=cnt,bm;
k=-1;
while(bl<=bh){
bm=(bl+bh)/2;
if(r[bm]>m){ //not '>='
bh=bm-1;
k=bm;
}
else bl=bm+1;
}
r[k]=m;
}
}
printf("%d\n",cnt);
}
return 0;
}
posted on 2009-03-27 13:23
wolf5x 閱讀(139)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm_icpc