• <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 
            

            







            
	    
    




            






            

				

            






    
    







            
	   
	



亚洲国产二区三区久久|
久久这里有精品视频|
久久天天躁狠狠躁夜夜躁2O2O|
亚洲精品tv久久久久久久久|
亚洲AV日韩精品久久久久|
久久成人影院精品777|
久久综合伊人77777麻豆|
久久精品无码午夜福利理论片|
久久精品国产91久久综合麻豆自制|
久久久久久噜噜精品免费直播|
久久精品国产亚洲AV香蕉|
99久久精品影院老鸭窝|
四虎影视久久久免费观看|
久久精品无码专区免费青青
|
久久久一本精品99久久精品88|
久久精品国产亚洲av麻豆色欲|
久久久久久久综合综合狠狠|
国产精品欧美久久久天天影视|
中文字幕无码av激情不卡久久|
久久久精品免费国产四虎|
久久婷婷成人综合色综合|
亚洲精品综合久久|
久久精品国产欧美日韩|
久久99国产精品久久|
日韩精品久久久久久久电影蜜臀|
欧美一级久久久久久久大片|
久久亚洲精品视频|
久久久久成人精品无码中文字幕|
久久人妻无码中文字幕|
亚洲欧洲久久久精品|
久久久WWW成人|
久久综合狠狠综合久久97色|
国产福利电影一区二区三区久久久久成人精品综合
|
一本一本久久a久久精品综合麻豆|
久久精品无码专区免费东京热|
久久久精品国产免大香伊
|
国产一区二区久久久|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
国产亚洲精久久久久久无码77777|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
伊人色综合久久天天人手人婷|