又一次看错题……
原题：
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后，剩下的花的高度依次为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时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
1 ≤ n ≤ 100,000，0 ≤ hi ≤ 1,000,000，所有的hi随机生成，所有随机数服从某区间内的均匀分布。
看错题了，原题是1 ≤ i ≤ m/2，g2i > g2i-1，且g2i > g2i+1，我看成了gi > g2i-1，且gi > g2i+1（也就是排序二叉树）……，如果在2016NOIP出现我就挂了QAQ
于是这道题就是求一个一上一下的拐弯序列，妥妥的DP，贪心也行
DP的方程就是
if(a[i]>a[i-1]){ f1[i]=max(f2[i-1]+1,f1[i-1]); f2[i]=f2[i-1];}
else if(a[i]<a[i-1]){ f2[i]=max(f1[i-1]+1,f2[i-1]); f1[i]=f1[i-1];}
else{ f1[i]=f1[i-1]; f2[i]=f2[i-1];}
思路很简单，就不证明了，也可以顺推单调性，复杂度都是O（n）的
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
int n,a[];
int f1[],f2[];
int main(){//freopen("ddd.in","r",stdin);
cin>>n;
f1[]=f2[]=; a[]=read();
for(int i=;i<=n;i++){
a[i]=read();
if(a[i]>a[i-]){ f1[i]=max(f2[i-]+,f1[i-]); f2[i]=f2[i-];}
else if(a[i]<a[i-]){ f2[i]=max(f1[i-]+,f2[i-]); f1[i]=f1[i-];}
else{ f1[i]=f1[i-]; f2[i]=f2[i-];}
}
cout<<max(f1[n],f2[n])<<endl;
return ;
}