2013年NOIP全国联赛提高组 1043: 花匠（贪心，最长波动子序列）

题目链接：http://129.211.20.246/problem.php?id=1043

思路：

​ 求最长波动子序列。用pre，cur记录当前最长波动子序列最后两个点的值。注意将相邻重复的点只剩一个。

提供几组数据

2

1 2

ans=2

2

1 1

ans=1

4

1 4 1 4

ans: 4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll H[100005];
vector<ll> h;
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;++i) scanf("%lld",H+i);
    for(ll i=1;i<=n;++i)//相邻重复的只取一个
        if(i==1||(H[i]!=h[h.size()-1])) h.push_back(H[i]);
    ll pre,cur,ans=0;
    if(h.size()<=2)
        cout<<h.size()<<endl;
    else{
        pre=h[0],cur=h[1],ans=2;
        for(ll i=2;i<h.size();++i){
            if((cur-pre)*(h[i]-cur)<0){//出现拐点
                ans++;
                pre=cur;
                cur=h[i];
            }
            else
                cur=h[i];//这是一个单调的线
        }
        cout<<ans<<endl;
    }
    return 0;
}