B 起伏的排名 SRM 06

背景&&描述

    天才麻将少女KPM立志要在日麻界闯出一番名堂。

    在上个星期她打了n场麻将，每场麻将都有n名玩家。KPM自然记得自己的n次排名。

    KPM有高超的控分技巧，所以她的n次排名是1..n的一个排列。

   为了让妹子相信自己最近比赛状态起伏不定不宜外出，KPM想要从n场比赛里选出一个子序列，使得第一场排名>第二场的，第二场排名<第三场的，第三场的>第四场的....

    总之除了选出来的第一场，选出来的其他场的排名 要么<选出来的相邻两场的排名 要么>选出来的相邻两场的排名。并且第一场排名要>第二场的。

    你不需要输出具体的场次，只需要输出符合要求的子序列可能的最大长度就好了。。

    只选一场也是满足条件的。

输入格式

第一行一个整数n。

第二行n个整数，表示n场的排名。

输出格式

一个整数，表示最大的长度。

样例输入

65 2 1 6 4 3

样例输出

4

数据范围与约定

• 对于100%的数据:

 

这道题就是求一个 大小大小大小的序列 其中大小是相对于相邻两个数而言

我们可以分情况考虑答案

1. 前一个数是 ‘大’ （定义为last）那么我们下一个数一定要比他小 这时我们考虑当前数 （定义为now）

如果now<last 很明显符合 那么答案++

如果last>=now 那么前面小于last的以及后面能<last的同样能符合now 那么我们完全可以用now代替last

2 前一个数是 ‘下' 同1

所以这个问题就转换成了求拐点数 拐点数+1就是答案了 2333

#include
      
       #include
       
        #include
        
         using namespace std;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,ans=1,last,now,f;int main(){    n=read();     last=read(); f=1;    for(int i=1;i
         
          last&&f==-1) f=1,ans++;        last=now;    }    printf("%d\n",ans);    return 0;}