• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        




            
	
		
		
            

隨筆-38 
評(píng)論-23 
文章-0 
trackbacks-0

            
	

            

            
	
					


            
	
	
            簡(jiǎn)單的概括下 這題的意思就是求一個(gè)最長(zhǎng)上升子序列.由于number的數(shù)很多.用普通的n^2的DP求最長(zhǎng)上升子序列肯定會(huì)超時(shí)。。故采用二分查找的方法。

            

            #include<iostream>
            using namespace std;
            int num[40001],dp[40001],n;
            int DP()
            {
                            int len=1,left,right,mid;
                dp[            0]=num[0];
                            for(int i=1;i<n;i++)
                            {
                    right            =len-1,left=0;
                                while(left<=right)
                                {
                        mid            =(left+right)/2;
                                    if(num[i]<=dp[mid])
                            right            =mid-1;
                                    else
                            left            =mid+1;
                    }
                    dp[left]            =num[i];
                                if(left==len) len++;
                }
                cout            <<len<<endl;
                            return len;
            }
            int main()
            {
                            int T;
                cin            >>T;
                            while(T--&&cin>>n)
                            {
                                for(int i=0;i<n;i++)
                        cin            >>num[i];
                                int len=DP();
                }
                            return 0;
            }
            

	
            posted on 2009-04-01 13:14 米游 閱讀(330) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 
            

            







            
	    
    




            






            

				

            






    
    







            
	   
	



久久91综合国产91久久精品|
久久免费视频观看|
亚洲国产成人久久精品99
|
99久久99久久精品国产片|
国产精品嫩草影院久久|
久久亚洲国产精品123区|
99久久精品免费看国产一区二区三区
|
亚洲综合精品香蕉久久网|
久久人人爽人人爽人人av东京热|
久久中文字幕无码专区|
亚洲AV无码久久精品色欲|
国产日韩久久久精品影院首页|
无码人妻久久一区二区三区蜜桃
|
综合人妻久久一区二区精品|
77777亚洲午夜久久多喷|
亚洲国产婷婷香蕉久久久久久|
国内精品伊人久久久久av一坑
|
久久成人18免费网站|
综合人妻久久一区二区精品|
精品99久久aaa一级毛片|
亚洲乱码精品久久久久..
|
 久久综合狠狠综合久久激情 |
欧美亚洲国产精品久久|
国产91久久综合|
狠狠色丁香久久综合五月|
久久久久久精品免费免费自慰
|
欧洲成人午夜精品无码区久久|
久久成人精品|
国内精品免费久久影院|
AV无码久久久久不卡蜜桃|
午夜欧美精品久久久久久久|
亚洲国产精品无码久久久久久曰|
国产999精品久久久久久|
国产精品久久免费|
国产亚洲综合久久系列|
亚洲AV无码1区2区久久|
伊人久久大香线蕉综合Av|
久久精品中文无码资源站|
伊人久久一区二区三区无码|
日韩精品无码久久一区二区三|
久久人人超碰精品CAOPOREN|