1014 登山（最长上升子序列扩展）

浅浅的花香味﹌ 2022-09-11 12:30 158阅读 0赞

**1. 问题描述：**

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

**输入格式**

第一行包含整数N，表示景点数量。第二行包含N个整数，表示每个景点的海拔。

**输出格式**

输出一个整数，表示最多能浏览的景点数。

**数据范围**

2 ≤ N ≤ 1000

**输入样例：**

8  
186 186 150 200 160 130 197 220

输出样例：

4  
来源：[https://www.acwing.com/problem/content/description/1016/][https_www.acwing.com_problem_content_description_1016]

**2. 思路分析：**

分析题目我们可以得到三个信息点：

*  浏览景点的编号是递增的
 *  相邻的两个景点的海拔不能相同
 *  到某个位置开始下降的之后就不能够上升了

由这三个特点我们可以得到所有浏览景点类似于下图的形状，本质上是最长上升子序列问题， 类似于[acwing1017][]题，但是又有细微的不同。所以我们可以想到计算以当前位置结尾与开始的最长上升子序列和最长下降子序列长度的最大值，使用一维数组f和g来记录子序列的最大值，其中f\[i\]表示以h\[i\]结尾的最长上升子序列长度的最大值，g\[i\]表示以h\[i\]开始的最长下降子序列的长度的最大值（可以先预处理一下），h为景点的海拔高度，然后枚举以当前的位置i作为顶点求解出答案的最大值即可。

![20210916190604629.png][]

**3. 代码如下：**

if __name__ == "__main__":
        n = int(input())
        h = list(map(int, input().split()))
        f, g = [0] * n, [0] * n
        # 分别求解最长上升子序列与最长下降子序列
        for i in range(n):
            f[i] = 1
            for j in range(i):
                if h[i] > h[j]:
                    f[i] = max(f[i], f[j] + 1)
        for i in range(n - 1, -1, -1):
            g[i] = 1
            for j in range(n - 1, i, -1):
                if h[i] > h[j]:
                    g[i] = max(g[i], g[j] + 1)
        # 枚举一下答案以当前的位置为顶点的所有这种形状的最大值
        res = 0
        for i in range(n):
            # 因为当前顶点的位置加了两次所以需要减去1
            res = max(res, f[i] + g[i] - 1)
        print(res)

[https_www.acwing.com_problem_content_description_1016]: https://www.acwing.com/problem/content/description/1016/
[acwing1017]: https://blog.csdn.net/qq_39445165/article/details/120325948
[20210916190604629.png]: /images/20220828/50101ff7a29f4fa8b8e78c56a6e0ddbd.png