NOIP2013花匠(波动序列)

波动序列的定义不用多说，下面给出波动序列的求法。

#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int n,a[N],dp[N][2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);dp[1][0]=dp[1][1]=1;
    for(int i=2;i<=n;++i){
    if(a[i]>a[i-1])dp[i][1]=dp[i-1][0]+1;
    else dp[i][1]=dp[i-1][1];
    if(a[i]<a[i-1])dp[i][0]=dp[i-1][1]+1;
    else dp[i][0]=dp[i-1][0];
    }
    cout<<max(dp[n][1],dp[n][0]); 
    return 0;
}

这里有一个结论，就是存在一个最优解的末尾为数列的最后一个点。

证明：

假设当前是一个下降的最优的波动序列，遇到了下一个点。

1.当前高度与上一个的高度相等，那这两个点选谁也无所谓，直接用当前点覆盖上一个点。

2.当前高度比上一个高度低，那我也可以用这个点替换上一个点，因为当前是山谷，山谷越低，对于下一个点来说成为山峰的概率越大。

3.当前高度比上一个高度高，那我可以直接把这个点纳入这个序列，序列长度+1。

三种情况讨论完毕。

上升的情况同理。

证毕。