P1970 [NOIP2013 提高组] 花匠

 洛谷推荐

题目背景

NOIP2013 提高组 D2T2

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数 h1,h2,…,hnh_1,h_2,ldots,h_n。设当一部分花被移走后，剩下的花的高度依次为 g1,g2,…,gmg_1,g_2,ldots,g_m，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的 1≤i≤m21 le i le frac{m}{2}，有 g2i>g2i−1g_{2 i} > g_{2 i - 1}，同时对于所有的 1≤i≤m21 le i le frac{m}{2}，有 g2i>g2i+1g_{2 i} > g_{2 i + 1}；
条件 B：对于所有的 1≤i≤m21 le i le frac{m}{2}，有 g2i<g2i−1g_{2 i} < g_{2 i - 1}，同时对于所有的 1≤i≤m21 le i le frac{m}{2}，有 g2i<g2i+1g_{2 i} < g_{2 i + 1}。

注意上面两个条件在 m=1m = 1 时同时满足，当 m>1m > 1 时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入格式

第一行包含一个整数 nn，表示开始时花的株数。

第二行包含 nn 个整数，依次为 h1,h2,…,hnh_1,h_2,ldots,h_n，表示每株花的高度。

输出格式

输出一行，包含一个整数，表示最多能留在原地的花的株数。

输入输出样例

说明/提示

输入输出样例说明

有多种方法可以正好保留 33 株花，例如，留下第 11、44、55 株，高度分别为 55、11、22，满足条件 B。

数据范围

对于 20%20%的数据，n≤10n le 10；

对于 30%30%的数据，n≤25n le 25；

对于 70%70%的数据，n≤1000n le 1000，0≤hi≤10000 le h_i le 1000；

对于 100%100%的数据，1≤n≤1051 le n le {10}^5，0≤hi≤1060 le h_i le {10}^6，所有的 hih_i 随机生成，所有随机数服从某区间内的均匀分布。

相关知识

花匠鲜花加盟
“花匠”
花匠怎么学
一名花匠包装设计
养花技巧：老花匠教你三招，如何嫁接花木提高存活率！
幼儿园课件：花匠种花
卤蛋英雄花匠角色攻略
养花技巧：老花匠教你这三招，如何嫁接花木提高存活率！
小花匠
花匠解释

原文链接: P1970 [NOIP2013 提高组] 花匠 https://www.huajiangbk.com/newsview529464.html