TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7978
  • 题目
  • P7978队列翻转
    限制 : 时间限制 : - MS   空间限制 : - KB
    问题描述

    每个星期四下午是信竞队的体育活动时间。这次何老板给大家安排的体育活动是做广播体操。
    $n$名队员站成一排,何老板发现,同学们的队形并不是按照从左往右以身高由低到高来排列的,当前的队形有碍观感,何老板决定调整一下队形,使得队列中按由低到高顺序排列的区域尽可能长。

    何老板调整队列的方法时,在队列中任意选择一个子序列,将子序列中的同学的位置翻转。例如:

    有9个同学,初始时的身高排列如下:
    
    1 6 2 3 4 3 5 3 4
    
    何老板选了其中四个同学:
    
    1 6 2 3 4 3 5 3 4
      ^         ^ ^ ^
    翻转后:
    
    1 4 2 3 4 3 3 5 6
      ^         ^ ^ ^
    

    何老板也比较懒,他只想进行一次翻转操作。他想知道,操作后,能够得到的最长一段按身高由低到高(不下降)排列的子序列有多长?

    输入格式

    第一行,一个整数$n$
    接下来$n$行,每行一个整数,第$i$行的整数表示左起第$i$名队员的身高。

    输出格式

    一个整数,表示经过一次翻转后,能得到的最长不下降子序列的长度。

    样例输入 1

    9
    1
    2
    3
    9
    5
    6
    8
    7
    4

    样例输出 1

    9

    样例解释: 
    第4,7,8,9四个位置构成的子序列翻转

    样例输入 2

    9








    4

    样例输出 2

    7

    样例解释:  
    翻转后,最长的不下降子序列是1 2 3 3 3 5 6

    提示

    $1<=n<=50$
    $1<=身高<=50$