1995605 2006-08-03 15:27:32 Accepted 1986 C++ 00:00.20 552K St.Crux 以前写过一遍。这个算法很不错，时间是O(nlogn)，空间是O(n)，使用了一个栈。 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;}  

评论