登山 - 题目列表

题目描述

按编号递增的顺序浏览 $N$ 个景点，不能连续浏览海拔相同的两个景点，且一旦开始下山就不再向上走。给定 $N$ （ $2 \le N \le 1000$ ）和各景点海拔，求最多能浏览的景点数。

输入第一行为 $N$ ，第二行为 $N$ 个海拔；输出最多能浏览的景点数。样例输入 8 与 186 186 150 200 160 130 197 220，输出 4。

思路

即求最长的「先严格上升、后严格下降」子序列。枚举峰顶 $i$ ：up[i] 为以 $i$ 结尾的最长严格上升长度，down[i] 为从 $i$ 开始向右的最长严格下降长度（把序列反转后跑同一个 LIS，再把结果翻回原下标）。峰顶在两侧各被数一次，故答案为 $\max_i(up[i]+down[i]-1)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:15
# update_at: 2026-09-30 03:15

import sys


def strictly_rising_lengths(heights: list[int]) -> list[int]:
    """dp[i] = 以 heights[i] 结尾的最长「严格上升」子序列长度（经典 O(n^2) LIS）。"""
    dp: list[int] = []
    for i, h in enumerate(heights):
        # 前面所有比自己矮的位置都能接到 h 后面；都没有就只能自己当起点，长度 1
        dp.append(1 + max((dp[j] for j in range(i) if heights[j] < h), default=0))
    return dp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                                     # 景点数，2 <= n <= 1000
    heights = [next(data) for _ in range(n)]           # 按游览顺序给出的海拔

    up = strictly_rising_lengths(heights)              # up[i]：从左端走到 i 且一路向上的最多景点数
    down = strictly_rising_lengths(heights[::-1])[::-1]  # down[i]：从 i 一路向下走到右端的最多景点数
    # 反转序列后「向右下降」变成「向右上升」，同一份 DP 直接复用，结果再翻回原下标

    # 峰顶 i 在 up、down 里各被数了一次，所以以 i 为峰能浏览 up[i] + down[i] - 1 个景点
    print(max(u + d - 1 for u, d in zip(up, down)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:50
 * update_at: 2026-10-05 07:50
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

ll a[MAXN];     // 按游览顺序给出的景点海拔
ll up[MAXN];    // up[i]：以 i 结尾的最长严格上升子序列长度
ll down[MAXN];  // down[i]：从 i 开始向右的最长严格下降子序列长度

// 对序列 b[1..n] 求以每个位置结尾的最长严格上升子序列长度
void lis_strict(ll b[], ll dp[], ll n) {
    for (ll i = 1; i <= n; i++) {
        dp[i] = 1; // 至少包含自己
        for (ll j = 1; j < i; j++) {
            if (b[j] < b[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    lis_strict(a, up, n); // 正向：以 i 结尾的最长严格上升段

    // 反转海拔后「向右严格下降」变成「向右严格上升」，复用同一份 LIS
    ll rev[MAXN];    // 反转后的海拔
    ll rev_dp[MAXN]; // 反转序列上每个位置结尾的最长严格上升长度
    for (ll i = 1; i <= n; i++) {
        rev[i] = a[n - i + 1];
    }
    lis_strict(rev, rev_dp, n);
    for (ll i = 1; i <= n; i++) {
        down[i] = rev_dp[n - i + 1];
    }

    ll ans = 0; // 最多能浏览的景点数
    for (ll i = 1; i <= n; i++) {
        ll total = up[i] + down[i] - 1; // 峰顶被两侧各数了一次，减 1
        if (total > ans) {
            ans = total;
        }
    }

    cout << ans << "\n";
    return 0;
}

登山

目录

题目描述

思路

参考代码