• <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 
評論-23 
文章-0 
trackbacks-0

            
	

            

            
	
					


            
	
	
            簡單的概括下 這題的意思就是求一個最長上升子序列.由于number的數很多.用普通的n^2的DP求最長上升子序列肯定會超時。。故采用二分查找的方法。

            

            #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 米游 閱讀(333) 評論(0)  編輯 收藏 引用  所屬分類: ACM 
            

            







            
	    
    




            






            

				

            






    
    







            
	   
	



亚洲精品午夜国产VA久久成人|
无码专区久久综合久中文字幕|
国内精品久久久久影院免费|
久久国产精品久久久|
精品国产综合区久久久久久|
怡红院日本一道日本久久
|
中文字幕热久久久久久久|
国内精品久久久久久久久电影网|
99久久无色码中文字幕|
久久久久无码中|
久久精品人人做人人爽电影|
亚洲精品第一综合99久久|
国产韩国精品一区二区三区久久|
久久久久亚洲爆乳少妇无|
久久精品国产91久久麻豆自制|
精品综合久久久久久97|
激情五月综合综合久久69|
国产精品久久久久久久久免费|
久久人人爽人人爽人人av东京热
|
久久精品亚洲精品国产色婷|
亚洲狠狠久久综合一区77777
|
伊人久久亚洲综合影院|
久久综合九色综合欧美狠狠|
狠狠综合久久综合中文88|
无码人妻精品一区二区三区久久|
久久e热在这里只有国产中文精品99|
久久亚洲日韩精品一区二区三区|
欧美日韩精品久久久免费观看|
久久激情五月丁香伊人|
成人精品一区二区久久久|
97久久精品人人澡人人爽|
久久综合九色综合97_久久久|
91精品国产色综合久久|
久久99久久99小草精品免视看|
久久亚洲春色中文字幕久久久|
久久偷看各类wc女厕嘘嘘|
久久婷婷五月综合色高清|
亚洲国产另类久久久精品|
亚洲国产精品无码久久SM|
精品国产乱码久久久久久郑州公司|
久久久亚洲欧洲日产国码二区
|