[NOIP2013 D2 T2]花匠(贪心)

题目

描述

花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。
具体而言,栋栋的花的高度可以看成一列整数h1,h2..hn。设当一部分花被移走后,剩下的花的高度依次为g1,g2..gm,则栋栋希望下面两个条件中至少有一个满足:
条件 A:对于所有g(2i)>g(2i-1),g(2i)>g(2i+1)
条件 B:对于所有g(2i)<g(2i-1),g(2i)<g(2i+1)
注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。
请问,栋栋最多能将多少株花留在原地。

输入

输入的第一行包含一个整数n,表示开始时花的株数。
第二行包含n个整数,依次为h1,h2..hn,表示每株花的高度。

输出

输出一行,包含一个整数m,表示最多能留在原地的花的株数。

输入样例

1
2
5
5 3 2 1 2

输出样例

1
3

样例说明

有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。

数据范围

对于 20%的数据,n ≤ 10;
对于 30%的数据,n ≤ 25;
对于 70%的数据,n ≤ 1000,0 ≤ ℎi≤ 1000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ hi≤ 1,000,000,所有的hi 随机生成,所有随机数服从某区间内的均匀分布。


解题思路

题目要求的就是一个波浪形数列
将原数列按高度画出来会形成一个波浪形数列,而题目要求的就是只取波浪的波峰与波谷,注意处理一下相邻两个高度相同的情况。

复杂度 $O(n)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# include<cstdio>

using namespace std;

const int N = 100005;
int n, h[N], ans, cnt, pre = -1;

int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &h[i]);
if(n == 1) return puts("1"), 0;
if(n == 2) return puts(h[1] == h[2] ? "1" : "2"), 0;
int now = 1;
while(now < n && h[now] == h[now+1]) now++;
cnt += 2;
pre = h[now+1] > h[now];
for(int i = now+2; i <= n; i++){
if(h[i] == h[i-1]) continue;
cnt += ((h[i] > h[i-1]) != pre);
pre = h[i] > h[i-1];
}
printf("%d\n", cnt);
return 0;
}