首页 > 代码库 > [ZPG TEST 108] Antimonotonicity【贪心】

[ZPG TEST 108] Antimonotonicity【贪心】

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【贪心】