Posted on 2006-08-08 21:47
oyjpart 閱讀(763)
評(píng)論(3) 編輯 收藏 引用
PKU的Bridging Signals 在0(n*logn)的設(shè)計(jì)上寫的很復(fù)雜，無(wú)意見(jiàn)看到下面這個(gè)程序(by CQF） 受到啟發(fā)了！！ 呵呵
轉(zhuǎn)CQF大牛的算法：
1、建立一個(gè)棧stack，清空。{stack[i]表示當(dāng)前狀態(tài)下，所有長(zhǎng)度為i的子序中最后一個(gè)數(shù)的最小值}。//這個(gè)太漂亮了：cqf是大牛大牛大大牛呀：）
2、按先后順序循環(huán)序列的每一個(gè)數(shù)，用操作3修改當(dāng)前狀態(tài)
3、如果這個(gè)數(shù)不小棧頂或棧為空就++stack的長(zhǎng)度，否則就用二分法找出一個(gè)最小的i使得stack[i]>這個(gè)數(shù).將stack[i]更新為這個(gè)數(shù)。{可以用二分法是因?yàn)閟tack是有序的}
4、輸出stack的長(zhǎng)度。{最長(zhǎng)不下子序長(zhǎng)度}
#include <cstdio>
#include <string>
int a[40000], c;
int main()
{
?int m, n, i, k;
?//freopen("in.txt", "r", stdin);
?scanf("%d", &m);
?for(i = 0; i < m; i ++)
?{
??memset(a, 0, sizeof(a));
??scanf("%d", &n);
??c = 0;
??for(k = 0; k < n; k ++)
??{
???int t;
???scanf("%d", &t);
???if(c == 0 || t > a[c - 1])
????a[c ++] = t;
???else
???{
????int l = 0, h = c - 1, mid = (l + h) / 2;
????while(l < h)
????{
?????if(a[mid] < t) l = mid + 1;
?????else if(a[mid] > t) h = mid;
?????mid = (l + h) / 2;
????}
????a[mid] = t;
???}
???//pa();
??}
??printf("%d\n", c);
?}
?return 0;
}