var n,a,b,i,k,s:longint;
begin
read(n,a);
for i:=2 to n do
begin
read(b);
if (b>a) and (k<>1) then
begin
k:=1;
inc(s);
end;
if (b<a) and (k<>-1) then
begin
k:=-1;
inc(s);
end;
a:=b;
end;
writeln(s+1);
end.
O(n)神模拟，不用数组的方法
滚动输入+记录前一次不等号方向+简单循环与条件判断语句及输入输出的使用

记录信息
评测状态 Accepted
题目 P1845 花匠
递交时间 2015-08-14 20:26:59
代码语言 C++
评测机 VijosEx
消耗时间 112 ms
消耗内存 912 KiB
评测时间 2015-08-14 20:27:00
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:15:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(f[i]>f[i-1]&&k||f[i]<f[i-1]&&!k)
^
foo.cpp:24:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(f[i]>f[i-1]&&k||f[i]<f[i-1]&&!k)
^
测试数据 #0: Accepted, time = 15 ms, mem = 908 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 912 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 908 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 908 KiB, score = 10
测试数据 #9: Accepted, time = 52 ms, mem = 904 KiB, score = 10
Accepted, time = 112 ms, mem = 912 KiB, score = 100

#include <iostream>
#include <stdio.h>
using namespace std;
int f[100010];
int main()
{
int k=1;
int ans1=1;
int ans2=1;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
for(int i=2;i<=n;i++)
{
if(f[i]>f[i-1]&&k||f[i]<f[i-1]&&!k)
{
ans1++;
k=!k;
}
}
k=0;
for(int i=2;i<=n;i++)
{
if(f[i]>f[i-1]&&k||f[i]<f[i-1]&&!k)
{
ans2++;
k=!k;
}
}
printf("%d",max(ans1,ans2));
}

找有多少个转折点就行了，代码本来可以简短，但为了看得懂……
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<memory.h>
using namespace std;

int n,a[100010],ans;

void init()
{
memset(a,0,sizeof(a));
scanf("%d",&n);
for (int i = 1; i <= n; ++ i)
scanf("%d",&a[i]);
}

void work()
{
bool up;
ans = 2;
while (a[ans] == a[1] && ans < n)
++ ans;
if (ans == n)
{
printf("1");
exit(0);
}
else
if (a[ans] > a[1])
up = false;
else
up = true;
ans = 1;
for (int i = 2; i <= n; ++ i)
{
if (a[i] == a[i-1])
continue;
if (up && a[i] < a[i-1])
{
up = false;
++ ans;
}
if (!up && a[i] > a[i-1])
{
up = true;
++ ans;
}
}
printf("%d",ans);
}

int main()
{
init();
work();
return 0;
}

P1845花匠
Accepted

记录信息

评测状态 Accepted
题目 P1845 花匠
递交时间 2014-11-03 21:05:44
代码语言 C++
评测机 上海红茶馆
消耗时间 92 ms
消耗内存 956 KiB
评测时间 2014-11-03 21:05:45

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 952 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 952 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 952 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 952 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 952 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 956 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 956 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 952 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 952 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 948 KiB, score = 10

Accepted, time = 92 ms, mem = 956 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int f[100000 + 2];
int sum , ans;
int i;
bool flag;
int num;

int main()
{
while( scanf( "%d" , &n ) != EOF )
{
ans = n;
num = 0;
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &f[i] );
i = 2;
if( f[1] > f[0] )
flag = 0;
else if( f[1] < f[0] )
flag = 1;
else
for( ; i < n ; i++ )
if( f[i] == f[i - 1] )
ans--;
else
{
if( f[i] > f[i - 1] )
flag = 0;
else
flag = 1;
break;
}
sum = 2;
for( ; i < n ; i++ )
if( f[i] != f[i - 1] )
if( !flag )
if( f[i] > f[i - 1] )
{
num = max( f[i] , f[i - 1] );
sum++;
}
else
{
if( sum > 2 )
ans -= ( sum - 2 );
flag = !flag;
sum = 2;
num = f[i];
}
else
if( f[i] < f[i - 1] )
{
num = min( f[i] , f[i - 1] );
sum++;
}
else
{
if( sum > 2 )
ans -= ( sum - 2 );
flag = !flag;
sum = 2;
num = f[i];
}
else
sum++;
if( sum > 2 )
ans -= ( sum - 2 );
cout << ans << endl;
}
return 0;
}

单调数列。。。

#include<cstdio>
int n,i,x=0,y,ans=1,flag=0;
int main()
{

scanf("%d%d",&n,&x);

for(i=1;i<n;i++)
{
scanf("%d",&y);
if(y>x&&flag!=1) {ans++;flag=1; }
if(y<x&&flag!=-1) {ans++;flag=-1; }
x=y;

}

printf("%d",ans);
return 0;
}
序列缩点，连续递减的点和连续递增的点是可以缩到一个代表性的点上的，比如说样例给的5 3 2 1 2，
可以缩成5,1,2或3,1,2或2,1,2，即5 3 2这三个连续递减的点实际上可以由一个点代替，1是一个转折点，
于是你也可以说是找转折点个数。
当找到转折点的个数后 后面必然有成立的点。用转折点的个数 加上后面成立的点的个数 加上必然有一个点满足条件(题目中有说过)就可以在O(n）的时间内找出答案。

#include<cstdio>
int n,h[100001],ans=0,flag=-1;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%d",&h[i]);
for(int i=1;i<n;++i)
{
if(h[i]>h[i-1]&&flag!=1){++ans;flag=1;}
if(h[i]<h[i-1]&&flag!=0){++ans;flag=0;}
}
printf("%d\n",ans+1);
return 0;
}
序列缩点，连续递减的点和连续递增的点是可以缩到一个代表性的点上的，比如说样例给的5 3 2 1 2，
可以缩成5,1,2或3,1,2或2,1,2，即5 3 2这三个连续递减的点实际上可以由一个点代替，1是一个转折点，
于是你也可以说是找转折点个数。
当找到转折点的个数后 后面必然有成立的点。用转折点的个数 加上后面成立的点的个数 加上必然有一个点满足条件(题目中有说过)就可以在O(n）的时间内找出答案。

#include <iostream>
#include <cstdio>
#define maxm(x,y) (x<y? y:x)
using namespace std;
const int maxn = 1000005;
int h[maxn] = {0}; //
int n;
int S1[maxn], S2[maxn] ;

int main(void)
{
cin>>n;
for(int i = 1; i <= n; i++)
cin>>h[i];
S1[1] = S2[1] = 1; //初始状态

for(int i = 2;i <= n; i++)
{
if(h[i] > h[i-1]) // case1
{
S1[i] = maxm(S1[i-1], S2[i-1]+1 );
S2[i] = S2[i-1];
}
else if (h[i] == h[i-1])// case2
{
S1[i] = S1[i-1];
S2[i] = S2[i-1];
}
else //case 3
{
S1[i] = S1[i-1];
S2[i] = maxm(S1[i-1]+1, S2[i-1] );
}
}

cout<<maxm(S1[n], S2[n]) ;
return 0;
}

var i,j,n,k,l,p,q:longint;
begin read(n);
if n<=2 then
begin
writeln(n);halt;end;
read(j,k);
for i:=3 to n do
begin read(l);
if (j<k)and(l<k) then inc(p);
if (j>K)and(l>K) then inc(q);
if l=k then continue;
j:=k;k:=l;end;
writeln(p+q+2);
end.

program flower;
var ans,i,j,k,n,m:longint;
a,h:array[0..100000] of longint;
procedure datain;
begin
readln(n);
for i:=1 to n do
read(h[n]);
end;

procedure data;
var i,j,k:longint;
begin
fillchar(a,sizeof(a),0);
m:=1;
for i:=2 to n do
if h[i-1]=h[i] then begin h[i-1]:=0; inc(m); end;
if m=n then begin write(1);halt;end;
ans:=2;k:=1;
for i:=1 to n do
if h[i]<>0 then begin a[k]:=h[i]; inc(k);end;
for i:=2 to n-1 do
if ((a[i-1]<a[i]) and (a[i]>a[i+1])) or ((a[i-1]>a[i])and (a[i]<a[i+1]))
then inc(ans);
writeln(ans);
end;

begin
datain;
data;
end.

问一下哪里错了~

O(n)做法：初始化ans=1（保留第一个数据），因为连续单调的一段数据中最多只能保留一个，所以从第2个数据起如果一直单调则一直扫，直到出现拐点则ans+1，然后继续向后扫，循环往复直至扫完，最后输出ans。
注意：此处的单调并非指严格单调，出现相邻数据相同的情况也算单调。

O(n)的方法。
首先读进去的时候把所有相邻的重复的删去只留下一个。
然后如果删去到最后只剩下一个数就输出1.
否则，初始化ans=2，从第2个到第n-1个扫一遍，找出
a[i-1]<a[i]>a[i+1]或者a[i-1]>a[i]<a[i+1]的，每找到一个inc(ans)
然后输出ans即可。
贪心方法，就是找拐点...考试的时候跟dp的对拍发现好像是对的....

#include <cstdio>
#include <cstdlib>
#include <string.h>
#define MAX(A,B) ((A>B)?A:B)
using namespace std;

const int MAXN = 100001;

int n;
int data[MAXN];
int dp[MAXN]; bool flag[MAXN];

inline int find_forward(int p_this, bool position){
for(int i = p_this-1 ; i >= 0; --i){
if(data[i] == data[p_this]) continue;
if(position == flag[i] && ((data[p_this] < data[i]) == position)) return i;
}
return 0;
}

int main(){
memset(dp, 0, sizeof(dp));
memset(flag, 0 ,sizeof(flag));

scanf("%d", &n);

for(int i = 0; i < n; ++i)
scanf("%d", &data[i]);

dp[0] = 1;
for(int i = 1; i < n; ++i){
int i_big, i_small;
i_big = find_forward(i, true);
i_small = find_forward(i, false);

dp[i] = MAX(dp[i_big],dp[i_small]) + 1;
flag[i] = data[i] > data[(dp[i_big]>dp[i_small])?i_big:i_small];
}

printf("%d", dp[n-1]);
return 0;
}

DP点此查看题解