链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1597
题意：
| Description |
| 给一个长度为n的整数序列A0,A1,......An-1,找出最长的非递增子序列的长度 |
| Input |
|
输入第一行为数据组数T(T<=20)。 每组数据的第一行为整数的个数n(2<=n<=1000)，第二行为n个绝对值不超过150000的整数。 |
| Output |
| 对于每组数据，输出最长的非递增子序列的长度。 |
| Sample Input |
|
2 3 1 1 3 4 -1 4 3 2 |
| Sample Output |
|
2 3 |
这类都是属于序列问题，不过常见的就是最长单调子序列，这里只是换了一下，不过方法都还是一样的；
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXN 1000+10 int a[MAXN], x[MAXN]; int main() { int n, cas; scanf("%d", &cas); while(cas--){ memset(x, 0, sizeof(x)); scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=0; i<n; i++) x[i] = 1; int max = 1; for(int i=1; i<n; i++) { for(int j=i-1; j>=0; j--) { if(a[j] >= a[i]) { if(x[j]+1 > x[i]) x[i] = x[j]+1; } } if(max < x[i]) max = x[i]; } printf("%d\n", max); } return 0; }
HLG 1597(最长飞递增子序列),布布扣,bubuko.com
原文：http://blog.csdn.net/keshacookie/article/details/21129129