花匠

题目链接: http://acm.ocrosoft.com/problem.php?cid=1629&pid=54

题目描述：

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数ℎ1, ℎ2, … , ℎn。设当一部分花被移走后，剩下的花的高度依次为g1, g2, … , gm，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的1 ≤ i ≤ m/2，g2i > g2i−1，且g2i > g2i+1；

条件 B：对于所有的1 ≤ i ≤ m/2，g2i < g2i−1，且g2i < g2i+1。

注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

【数据范围】

对于 20%的数据，n ≤ 10； 对于 30%的数据，n ≤ 25；

对于 70%的数据，n ≤ 1000，0 ≤ hi≤ 1000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ hi≤ 1,000,000，所有的?n随机生成，所有随机数服从某区间内的均匀分布。

输入

输入文件为flower.in。

输入的第一行包含一个整数

输出

输出文件为flower.out。 

输出一行，包含一个整数

样例输入：

5
5 3 2 1 2

样例输出：

3

提示

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

思路：不管是条件a还是条件b，它所表达的意思都是要使最后的花是一个波动的数列，也即最后的数列是由原先数列的转折点组成的。代码就是找出每个转折点的过程。

代码：

#include<stdio.h>
int max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int main()
{
    int n,a,b,r=1,d=1;
    scanf("%d",&n);
    scanf("%d",&a);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&b);
        if(b>a) r=max(r,d+1);//输入的点是高点
        if(b<a) d=max(d,r+1);//输入的点是低点
        a=b;
    }
    printf("%d",max(r,d));
    return 0;
}