【NOIP2013提高组 day2】花匠

2019/7/23 22:05:08 人评论 次浏览 分类:学习教程

知识共享许可协议 版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons)

在这里插入图片描述

分析

直接贪心(据说动态规划也可以orz)
保留的花要么左右两边高度都比它高,要么左右两边高度都比它低。
因此一段连续上升的序列和一段连续下降的序列只保留一个转折点。
注意答案还要加开头和结尾的点。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=100050;
int n,a[N],ans;
int read(){
	int sum=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
    	if(ch=='-')f=-1;
    	ch=getchar();
	}
	 while(ch>='0'&&ch<='9')
    {
    	sum=(sum<<3)+(sum<<1)+ch-'0';
    	ch=getchar();
	}
	return sum*f;
}
int main(){
	freopen("flower.in","r",stdin);
	freopen("flower.out","w",stdout);
	n=read();
	a[1]=read();
	ans=1;
	int flag=-1;
	for(int i=2;i<=n;i++)
	{
		a[i]=read();
		if(i==n)ans++; 
		if(a[i]>a[i-1]){
			if(flag==0)ans++;
			flag=1;
		}
		if(a[i]<a[i-1]){
			if(flag==1)ans++;
			flag=0;
		}
	}
	cout<<ans;
	return 0;
} 

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->