直接找拐点就好了。。。

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int n,a[100001],flag=-1,ans=1;
    cin>>n;
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        if ( i >= 2 ) {
            if (a[i] > a[i-1] && flag != 1)
                ans++,flag=1;
            if (a[i] < a[i-1] && flag != 0)
                ans++,flag=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

对于每一个单调区间（不论是不下降区间还是不上升区间），可以确定这些区间里面只能选一个点（可以理解为其中的最值点即该区间的最优解）。
本题只求数量不求序列，那么我们**统计有多少个非严格单调区间即可**。
（如果要求序列，就在每个单调区间里面拿一个最值出来就好了。）
上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

int h[100001],n,ans=1;
bool flag;

int main()
{
    read(n);
    if(n==1) {printf("1"); return 0;}
    for (register int i=1;i<=n;++i) read(h[i]);
    flag=h[2]<h[1];
    for (register int i=2;i<=n;++i)
    {
        if(h[i]==h[i-1]) continue;
        if(flag)
        {
            if(h[i]<h[i-1]) ++ans,flag=false;
        } else {
            if(h[i]>h[i-1]) ++ans,flag=true;
        }
    }
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,x[100005];
int main(){
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
cin>>n;
n=1; cin>>x[0];
while(cin>>x[n])
if(x[n]!=x[n-1])n++;
for(int i=1;i<n-1;i++){
int a=x[i]-x[i-1];
int b=x[i]-x[i+1];
if(a>0&&b>0||a<0&&b<0)
cnt++;
}
if(n==1)cout<<1;
else cout<<cnt+2<<endl;
return 0;
}

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int ans1,ans2;
int n,a,b;

int main()
{
ans1=ans2=1;
scanf("%d%d",&n,&a);
for (int i=2;i<=n;i++)
{
scanf("%d",&b);
if (b>a) ans1=ans2+1;
else
if (b<a) ans2=ans1+1;
a=b;
}
cout<<max(ans1,ans2)<<endl;
return 0;
}

先选第一个和最后一个
然后直接找拐点即可

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int main()
{
    int n,s=1;
    scanf("%d",&n);
    a[0]=58654535;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]!=a[i-1])
        {
            b[s]=a[i];
            s++;
        }
    }
    if(s==2)
    {
        printf("1");
        return 0;
    }
    n=s-2;
    s=1;
    for(int i=2;i<=n;i++)
    {
        if((b[i]>b[i-1]&&b[i]>b[i+1])||(b[i]<b[i-1]&&b[i]<b[i+1]))
        {
            s++;
        }
    }
    printf("%d",s+1);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 100005;

int f[M][2], h[M];

int main()
{
int n, ans = 1;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &h[i]);
f[1][0] = f[1][1] = 1;
for(int i = 2; i <= n; i++){
for(int j = max(1, i - 50); j < i; j++)
if(h[j] < h[i])
f[i][0] = max(f[j][1] + 1, f[i][0]);
for(int j = max(1, i - 50); j < i; j++)
if(h[j] > h[i])
f[i][1] = max(f[j][0] + 1, f[i][1]);
ans = max(ans, f[i][1]);
ans = max(ans, f[i][0]);
}
printf("%d", ans);
return 0;
}
DP

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/5664673.html

#include<iostream>
using namespace std;
int h[100001];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,mmax=0,mmax1=1,mmax2=1;
    bool k=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=2;i<=n;i++)
    {
        if(h[i]<h[i-1]&&k)
        {
            mmax1++;
            k=!k;
        }
        if(h[i]>h[i-1]&&!k)
        {
            mmax1++;
            k=!k;
        }
    }
    k=1;
    for(int i=2;i<=n;i++)
    {
        if(h[i]>h[i-1]&&k)
        {
            mmax2++;
            k=!k;
        }
        if(h[i]<h[i-1]&&!k)
        {
            mmax2++;
            k=!k;
        }
    }
    mmax=max(mmax1,mmax2);
    cout<<mmax;
    return 0;
}

第一株花一定可以保留，然后后面的花要么增要么减只需求出后面的话中的转折点即可；

#include<iostream>
#include<cstdio>
using namespace std;
int n,h[100005];
int main(){
int i,res1=1,res2=1,k,ans;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&h[i]);
k=0;
for(i=2;i<=n;i++){
if(h[i]<h[i-1]&&!k){
res1++;k=!k;
}
if(h[i]>h[i-1]&&k){
res1++;
k=!k;
}
}
k=1;
for(i=2;i<=n;i++){
if(h[i]>h[i-1]&&k){
res2++;k=!k;
}
if(h[i]<h[i-1]&&!k){
res2++;
k=!k;
}
}
ans=max(res1,res2);
printf("%d",ans);
return 0;
}


5分钟想出来的 混了70分
#include <cstdio>
#define Q 100100

int n,a[Q];
int f1[Q]={0},f2[Q]={0};
//f1[x] x为极大值点时的最优值

//当p为极大值点时k=1
void dfs(int p,int k,int step){
if(k==1) f1[p]=step;
if(k==0) f2[p]=step;
if(k==1){
for(int i=p+1;i<=n;i++){
if(f2[i]>=step+1) continue;
if(a[p]>a[i])
dfs(i,0,step+1);
}
}
if(k==0){
for(int i=p+1;i<=n;i++){
if(f1[i]>step+1) continue;
if(a[p]<a[i])
dfs(i,1,step+1);
}
}
}

int main(){
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
if(f1[i]==0||f2[i]==0){
if(f1[i]==0) dfs(i,1,1);
if(f2[i]==0) dfs(i,0,1);
}
}
int ans=0;
for(int i=n;i>=1;i--){
ans=ans>f1[i]?ans:f1[i];
ans=ans>f2[i]?ans:f2[i];
}
printf("%d\n",ans);
return 0;
}

O(n)贪心，走到最高点就往下走，走到最低点就往上走，证明可以用局部调整搞定。
```c++
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 100000 + 10;

int n;
int ans;
int h[maxn];

void solve () {
vector<int> tmp1, tmp2;
tmp1.push_back(h[0]); tmp2.push_back(h[0]);
for (int i = 1; i < n; i++) {
int cur = h[i];
if (tmp1.size()&1) {
if (cur <= tmp1[tmp1.size()-1]) tmp1[tmp1.size()-1] = cur;
else tmp1.push_back(cur);
} else {
if (cur >= tmp1[tmp1.size()-1]) tmp1[tmp1.size()-1] = cur;
else tmp1.push_back(cur);
}

if (tmp2.size()&1) {
if (cur >= tmp2[tmp2.size()-1]) tmp2[tmp2.size()-1] = cur;
else tmp2.push_back(cur);
} else {
if (cur <= tmp2[tmp2.size()-1]) tmp2[tmp2.size()-1] = cur;
else tmp2.push_back(cur);
}
}

// for (int i = 0; i < tmp1.size(); i++) cout << tmp1[i] << " "; cout << "\n";
// for (int i = 0; i < tmp2.size(); i++) cout << tmp2[i] << " "; cout << "\n";
ans = max(tmp1.size(), tmp2.size());
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) cin >> h[i];
solve();
cout << ans << "\n";
return 0;
}
```

尽管正解是遇到拐点ans + 1，复杂度O(N)，但是还是说一下网上没有见过的方法

我用的是Fenwick树，核心思想还是dp。开两个Fenwick树数组，分别记录花的高度<=该点的最大值，与>=该点的最大值，然后O(NlogMAXH)过~

这就一个水题啊=-= 复制粘贴复制粘贴 搞定
我们把一个极大、连续、不降的子序列看作一个区间，那么上一个区间的数肯定要选这个区间的数（如果这个区间的数可以选这个区间的数，那么这个区间可以分成两个更小的区间），这样才能保证最优解。
然后乱搞
cpp
#include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;++i)
#define MAXN 100001
int n, a[MAXN];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
/*_-_-_-_ style*/
int i=1,ans = 0;
while (i <= n) {
int last = a[i];
while (a[i] >= last && i <= n) {
last = a[i ++];
}
++ ans;
if (i>n) break;
last=a[i];
while (a[i] <= last && i <= n){
last = a[i ++];
}
++ ans;
}
i = 1;
int ans_ = 0;
/*-_-_-_- style*/
while (i <= n) {
int last = a[i];
while (a[i] <= last && i <= n) {
last = a[i ++];
}
++ ans_;
if (i>n) break;
last=a[i];
while (a[i] >= last && i <= n){
last = a[i ++];
}
++ ans_;
}
cout << max(ans, ans_);
}


那些什么O(n)的做法实在是太厉害了...
弱菜只会N log N离散化+线段树……
用的是N ^ 2的DP方程，优化找MAX为log N

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100005
#define INF 12345678
#define s 131072
using namespace std;
struct flower{
int h,pos;
bool operator < (flower a) const {return h<a.h;}
}f[MAXN];
int n,hmax=1,h[MAXN];
int tl[s<<1],th[s<<1];

inline int findhi(int l) {
int ans=0;
for (int r=s<<1;l^r^1;l>>=1,r>>=1) {
if ((l&1)^1) ans=max(ans,th[l^1]);
if (r&1) ans=max(ans,th[r^1]);
}
return ans;
}
inline int findlow(int r) {
int ans=0;
for (int l=s;l^r^1;l>>=1,r>>=1) {
if ((l&1)^1) ans=max(ans,tl[l^1]);
if (r&1) ans=max(ans,tl[r^1]);
}
return ans;
}
inline void updatelow(int x,int d) {
for (tl[x+=s]=d;(x>>=1)>0;)
tl[x]=max(tl[x<<1],tl[(x<<1)^1]);
}
inline void updatehi(int x,int d) {
for (th[x+=s]=d;(x>>=1)>0;)
th[x]=max(th[x<<1],th[(x<<1)^1]);
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",&f[i].h);
f[i].pos=i;
}
sort(f+1,f+n+1);
f[0].pos=-1;
for (int i=1;i<=n;i++) {
if (f[i].h!=f[i-1].h) hmax++;
h[f[i].pos]=hmax;
}
for (int i=1;i<=n;i++) {
int lnow=findhi(h[i]+s)+1;
if (tl[s+h[i]]<lnow) updatelow(h[i],lnow);
int hnow=findlow(h[i]+s)+1;
if (th[s+h[i]]<hnow) updatehi(h[i],hnow);
}
printf("%d\n",max(tl[1],th[1]));
return 0;
}

注意判重，例如：2 1 1 1 2，正解为3，而不是0

我蠢了。一直以为n的算法是DP。但是想不明白。好吧。我把2个思路都说下吧....

1：DP，很显然可以DP，我们分2种情况讨论，先上升和先下降。建个100000*3的数组，第一个是原值。第二，三个是DP数组。于是我们很容易得出一个类似于求最长单调子序列的DP。枚举每个值。再倒着枚举。

注意DP的边界条件。

时间复杂度是n^2只能拿70分 ,应该是可以枚举所有状态的。

2：楼下各位说的N的枚举法。其实这个就是求转折点= =因为一行单调的数可以压缩成为一个数。如5 4 3 2可以就压缩成一个5或者一个1= =因此只要后面有转折点，一点可以从5 4 3 2选出一个数让序列波动起来。

时间复杂度是n，秒杀。

刚刚写了个DP。没想到DP居然能拿80分。
建个100000*3的数组。A[I,2]表示这个数之前取小于号序列最长值。接下来这个序列需要上升。A[I,3】表示一个序列之前取了大于号的最大值，然后这个数需要下降。

2个状态转移：
a[i,3]:=max(a[i,3],a[j,2]+1);
a[i,2]:=max(a[i,2],a[j,3]+1);
你会发现2个数组好像是在交叉转移的= =，然后分别求出A[I,2] A[I,3]的最大值。比较输出即可

给出2个程序
###pascal code DP
program P1845;
uses math;
var a:array[1..100000,1..3] of longint;
i,n,j,ans1,ans2:longint;
begin
read(n); for i:=1 to n do begin read(a[i,1]); a[i,2]:=1; a[i,3]:=1; end;
ans1:=0; ans2:=0;
for i:=2 to n do
for j:=i downto 1 do
begin
if (a[i,1]>a[j,1]) then a[i,3]:=max(a[i,3],a[j,2]+1);
if (a[i,1]<a[j,1]) then a[i,2]:=max(a[i,2],a[j,3]+1);
end;
for i:=1 to n do ans1:=max(a[i,2],ans1);
for i:=1 to n do ans2:=max(a[i,3],ans2);
write(max(ans1,ans2));
end.

###pascal code n扫描
program P1845;
uses math;
var a:array[1..100000] of longint;
ans1,ans2,i,d,n:longint;
begin
read(n); for i:=1 to n do read(a[i]);
d:=1; ans1:=1; ans2:=1;
for i:=2 to n do
begin
if (d=1) and (a[i]>a[i-1]) then begin inc(ans1); d:=2; end;
if (d=2) and (a[i]<a[i-1]) then begin inc(ans1); d:=1; end;
end;
d:=2;
for i:=2 to n do
begin
if (d=1) and (a[i]>a[i-1]) then begin inc(ans2); d:=2; end;
if (d=2) and (a[i]<a[i-1]) then begin inc(ans2); d:=1; end;
end;

write(max(ans1,ans2));
end.

#include <cstdio>
using namespace std;
int n , h[ 100005 ] , ans1 , ans2 , tot , a[ 100005 ];
int main(){
freopen( "flower.in" , "r" , stdin );
freopen( "flower.out" , "w" , stdout );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &h[ i ] );
tot = 1;
a[ tot ] = h[ 1 ];
for( int i = 2 ; i <= n ; i++ )
if ( h[ i ] != h[ i - 1 ] )
a[ ++tot ] = h[ i ];
for( int i = 2 ; i < tot ; i++ ){
if ( a[ i ] > a[ i - 1 ] && a[ i ] > a[ i + 1 ] ) ans1++;
if ( a[ i ] < a[ i - 1 ] && a[ i ] < a[ i + 1 ] ) ans2++;
}

printf( "%d" , ans1 + ans2 + 2 );
fclose( stdin );
fclose( stdout );
return 0;
}

pascal AC 标程
var
n,i,j,len,o:longint;
t:boolean;
h:array[1..100000]of longint;
begin
readln(n);
for i:=1 to n do
read(h[i]);
j:=h[1];
len:=1;
for i:=2 to n do
if h[i]<>j then break;
if h[i]>j then t:=true
else t:=false;
j:=h[i];
o:=i+1;
inc(len);
for i:=o to n do
if t then
begin
if h[i]<j then
begin
inc(len);
t:=not t;
end;
j:=h[i];
end
else
begin
if h[i]>j then
begin
inc(len);
t:=not t;
end;
j:=h[i];
end;
writeln(len);
end.

思维难度大的题目
代码往往都很简单
这个题目 就是在给定的数列中求一个最长的波动序列
我们可以直接枚举转折点的个数
用d来表示当前要上升还是要下降
d=1 d=2分别表示两种状态 和为3
所以由当前状态向下一状态专一的时候 只需用3-d即可
另外d初始值要分2种情况
因为题目给了2个条件
O(N)枚举2次 输出较大的即可

测试数据 #0: Accepted, time = 3 ms, mem = 1156 KiB, score = 10
测试数据 #1: Accepted, time = 4 ms, mem = 1152 KiB, score = 10
测试数据 #2: Accepted, time = 3 ms, mem = 1156 KiB, score = 10
测试数据 #3: Accepted, time = 3 ms, mem = 1156 KiB, score = 10
测试数据 #4: Accepted, time = 1 ms, mem = 1160 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1156 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1160 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1156 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1156 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1160 KiB, score = 10
Accepted, time = 60 ms, mem = 1160 KiB, score = 100
代码
var
a:array[0..100000] of longint;
d,n,i,ans,max:longint;
begin
read(n);
for i:=1 to n do read(a[i]);
d:=1; ans:=1;
for i:=1 to n-1 do
case d of
1: if a[i]>a[i+1] then begin inc(ans); d:=3-d; end;
2: if a[i]<a[i+1] then begin inc(ans); d:=3-d; end;
end;
d:=2; max:=1;
for i:=1 to n-1 do
case d of
1: if a[i]>a[i+1] then begin inc(max); d:=3-d; end;
2: if a[i]<a[i+1] then begin inc(max); d:=3-d; end;
end;
if ans>max then writeln(ans) else writeln(max);
end.

O(n)秒，扫两遍

编译成功

测试数据 #0: Accepted, time = 8 ms, mem = 908 KiB, score = 10
测试数据 #1: Accepted, time = 6 ms, mem = 908 KiB, score = 10
测试数据 #2: Accepted, time = 6 ms, mem = 908 KiB, score = 10
测试数据 #3: Accepted, time = 9 ms, mem = 908 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 904 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 908 KiB, score = 10
测试数据 #6: Accepted, time = 1 ms, mem = 908 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 904 KiB, score = 10
测试数据 #9: Accepted, time = 27 ms, mem = 908 KiB, score = 10
Accepted, time = 102 ms, mem = 912 KiB, score = 100

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define N 100010
#define INF 0x7fffffff
int n;
int A[N],Ans;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
A[i]=read();
}
int pos=0,last=INF;
for(int i=1;i<=n;i++)
{
if(pos%2==0)
{
if(A[i]>=last)
last=A[i];
else
{
last=A[i];
pos++;
}
}
else
{
if(A[i]<=last)
last=A[i];
else
{
last=A[i];
pos++;
}
}
}
Ans=pos;
pos=0;last=-1;
for(int i=1;i<=n;i++)
{
if(pos%2==1)
{
if(A[i]>=last)
last=A[i];
else
{
last=A[i];
pos++;
}
}
else
{
if(A[i]<=last)
last=A[i];
else
{
last=A[i];
pos++;
}
}
}
Ans=max(Ans,pos);
cout<<Ans<<endl;
return 0;
}