首页 > 其他 > 详细

P1970 花匠

时间:2019-07-04 12:58:37      阅读:109      评论:0      收藏:0      [点我收藏+]

P1970 花匠

题解

这道题可以贪心做鸭

 

理解题意,说人话就是给出一个序列,让你找到最长波动序列的长度

 

把样例画出来也就是这样:

技术分享图片

然而实际你只需要保留波峰波谷的点就行了

 技术分享图片

 

 

 下面找最长波动序列

技术分享图片

 

PS:

当m>1的时候,下面的条件只能满足一个

技术分享图片

 

也就是数据

5 2 0 2 4 2 

ans=4

(不可以保留点2 3 4 5 6) 

 

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;
int a[maxn],n,m=1;
int flagup=0,flagdw=0;

inline int read()
{
    int ans=0;
    char last= ,ch=getchar();
    while(ch<0||ch>9) last=ch,ch=getchar();
    while(ch>=0&&ch<=9) ans=ans*10+ch-0,ch=getchar();
    if(last==-) ans=-ans;
    return ans;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
       a[i]=read();
    
    for(int i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])
        {
            flagup=1;
            if(flagdw)
            {
                m++;
                flagdw=0;
            }
        }
        if(a[i]<a[i-1])
        {
            flagdw=1;
            if(flagup)
            {
                m++;
                flagup=0;
            }
        }
    }
    
    printf("%d\n",m+1);
    
    return 0;
}

 

P1970 花匠

原文:https://www.cnblogs.com/xiaoyezi-wink/p/11131513.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!