oyjpArt ACM/ICPC算法程序設計空間

PKU的Bridging Signals 在0(n*logn)的設計上寫的很復雜，無意見看到下面這個程序(by CQF） 受到啟發(fā)了！！ 呵呵

轉(zhuǎn)CQF大牛的算法：

1、建立一個棧stack，清空。{stack[i]表示當前狀態(tài)下，所有長度為i的子序中最后一個數(shù)的最小值}。//這個太漂亮了：cqf是大牛大牛大大牛呀：）

2、按先后順序循環(huán)序列的每一個數(shù)，用操作3修改當前狀態(tài)

3、如果這個數(shù)不小棧頂或棧為空就++stack的長度，否則就用二分法找出一個最小的i使得stack[i]>這個數(shù).將stack[i]更新為這個數(shù)。{可以用二分法是因為stack是有序的}

4、輸出stack的長度。{最長不下子序長度}

#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;
}