T2:Antimonotonicity

(Antimonotonicity.pas/in/out 128M 1s)

给你1-N的一个排列，数列中的数字互不相等，要求找出最长的子序列a,满足a1>a2,a2<a3,a3>a4,a4<a5……

读入：

T    代表T组数据 T<=50

每组数据一行：    n   代表给你n个数，然后就是n个数 N<=30000

输出：

T行  每行一个数：

对于每组数据输出最长子序列的长度

Sample Input

4

5 1 2 3 4 5

5 5 4 3 2 1

5 5 1 4 2 3

5 2 4 1 3 5

Sample Output

1

2

5

3

唔，这一题没想到实在是不应该。最开始马上想到了dp做法，然而显然会T，尽管题解里说用数据结构优化一下是没问题的不过强烈不推荐。确实，有一个非常非常贪的做法。

上一个取的数是last，当前这个数是a，如果此时在抖动序列的下面的部分，那么如果a > last，则取a，并把last换成a，如果a < last，那么仍然把last换成a，但是不取a，这很显然，因为显然你把last换成一个更小的数是有利于下一次取数的！

#include <cstdio>

const int maxn = 30005;

int T, n, a, last, st, ans;

int main(void) {
	freopen("antimonotonicity.in", "r", stdin);
	freopen("antimonotonicity.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		ans = last = st = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &a);
			if (st) {
				if (a < last) {
					++ans;
					st = 0;
				}
				last = a;
			}
			else {
				if (a > last) {
					++ans;
					st = 1;
				}
				last = a;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

　　顺便说一句，这个题目名称的意思是“反单调性”。。。

[ZPG TEST 108] Antimonotonicity【贪心】