top1编程
← 返回上一页

P4963. 景点观光

时间限制
1000 ms
内存限制
64 MiB
难度
-
知识点
童程童美
知识点
动态规划基础
知识点
线性DP

题目描述

在即将到来的假期,学生们计划去香山游玩。他们手中有一份详细的香山地图,上面标注了 N 个不同的景点,编号从1~N。 他们计划按照先后的顺序来游览这些景点,确保每次游览的景点编号都比前一个游览的景点编号大。 在游览的过程中,需要遵守以下两个规则: 1、不连续游览相同海拔的景点:假设他们游览了一个海拔为X的景点,那么下一个游览的景点海拔必须不同于X。 2、一旦开始下山,就不再上山:游览过程应该是一个先上山再下山的过程,且一旦开始下山(即下一个景点的海拔比当前景点低),他们就不会再选择海拔更高的景点进行游览。 学生们希望在遵守以上规则的前提下,尽可能多地游览景点。请你帮助他们找出最多可能游览的景点数。

输入格式

第一行:N 景点数。 第二行:N 个整数,每个景点的海拔高度。

输出格式

最多能游览的景点数。

7
1 3 2 5 4 5 3
5