最长合法序列  Problem description 有k个整数A[1],A[2]...A[k],你需要从前往后选出若干个数,使得每一个后面的数都要大于或等于前面的 数.例如,对于系列1,4,2,5,2,3,选出1,2,2,3是合法的,但是选出4,2,3是不合法的.请你编写程序对于一个已知系列,求出最长的合法系列的数的个数.  Input 第一行为n，表示n个测试序列; 第二行到第n+1行，每行开始第一个数为k,　k后面紧跟k个数A[1],A[2] ….A[k]。  Output 输出n行，每行输出一个整数，表示相应测试序列中最长的合法序列的数的个数。  Sample Input 212 13 45 23 53 23 88 123 3 125 10 87 896 1 4 2 5 2 3 Sample Output 64 Judge Tips 其中0  Problem Source CSU 1st Contest //我的代码 #include <stdio.h>#include <stdlib.h> struct Node{ int i; int n;}; int main(){ int    nTest,i,j,k,n,m,max; struct Node *p;  scanf("%d",&nTest); for(i = 0; i < nTest; i++){  scanf("%d",&n);  p = (struct Node*)malloc(sizeof(struct Node)*n);  for(j = 0; j < n; j++){   scanf("%d",&p[j].i);   p[j].n = 1;  }  for(j = n - 1,max = 0; j >= 0; j--){   for(k = j + 1,m = 0; k < n; k ++){    if(p[j].i <= p[k].i && p[k].n > m)     m = p[k].n;   }   p[j].n += m;   if(p[j].n > max)    max = p[j].n;  }  printf("%d\n",max);  free(p); } return 0;}    

评论