Posted on 2006-08-08 21:47
oyjpart 阅读(758)
评论(3) 编辑 收藏 引用
PKU的Bridging Signals 在0(n*logn)的设计上写的很复杂，无意见看到下面这个程序(by CQF） 受到启发了！！ 呵呵
转CQF大牛的算法：
1、建立一个栈stack，清空。{stack[i]表示当前状态下，所有长度为i的子序中最后一个数的最小值}。//这个太漂亮了：cqf是大牛大牛大大牛呀：）
2、按先后顺序循环序列的每一个数，用操作3修改当前状态
3、如果这个数不小栈顶或栈为空就++stack的长度，否则就用二分法找出一个最小的i使得stack[i]>这个数.将stack[i]更新为这个数。{可以用二分法是因为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;
}