97久久久精品综合88久久,久久99国产精品久久99,久久人人爽人人人人片av

隨筆-38 評論-23 文章-0 trackbacks-0

pku 1631 DP(四)+二分查找

簡單的概括下這題的意思就是求一個最長上升子序列.由于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 米游閱讀(329) 評論(0) 編輯收藏引用所屬分類: ACM

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 有道難題... zoj 3211 Dream City 09.5.23 退役感言 RMQ ST算法 (區間最大(最小)值問題) 使用后綴數組解決zoj 3199 Longest Repeated Substring 線段樹求矩形覆蓋的周長 pku 1177 hdu 2816 即老菜鳥杯的1008題目 hdu 2813 即老菜鳥杯 1005題 hdu 2812 即老菜鳥杯 1004 hdu 2811 即老菜鳥杯 1003

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

ACM大牛

計算機圖形學

搜索

最新評論

閱讀排行榜

評論排行榜