posts - 43,  comments - 9,  trackbacks - 0
/*
    bupt 1032
    nlogn LIS
    注意!
    是最长不减序列(*1),而非最长升序列(*2) 
    则当t>=D[len]就直接更新len+1
    而t<D[len]时,应在D[1..len]中查找最大的j,满足D[j]<=A[t](在*2中,是满足D[j]<A[t]), 
    将t接在D[j]后得到更长的不减序列,同时更新D[j+1]=t
    这是我WA很多次的地方.对这个算法未理解透彻 
    附一组原先错误程序WA的数据:
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 阅读(117) 评论(0)  编辑 收藏 引用 所属分类: acm_icpc

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜