思路

• 对每条无向边 $(u,v)$，若 $h_u>h_v$，则将其定向为 $u\to v$；若 $h_v>h_u$，定向为 $v\to u$；若 $h_u=h_v$，这条边在可行路径中不可用（因为不严格下降），可忽略。
• 如此得到的有向图按海拔严格下降，因此不存在环，图是一个 DAG。
• 设动态规划数组 $dp[u]$ 表示从节点 $u$ 出发的满足条件的最长路径所包含的景点数量。转移为 $dp[u]=\max(1,1+\max_{(u\to v)} dp[v])$ 若 $u$ 没有出边，则 $dp[u]=1$。
• 计算顺序：将所有节点按海拔从小到大排序。因为对任意有向边 $u\to v$ 都有 $h_u>h_v$，所以 $v$ 会先于 $u$ 被处理，转移所需的 $dp[v]$ 已经就绪。
• 答案为 $\max_{u} dp[u]$。
• 复杂度：排序耗时 $O(n\log n)$，建边与 DP 为 $O(n+m)$，总体 $O(n\log n+m)$，空间 $O(n+m)$。

C++

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i];

    // 邻接表：将无向边按“高 -> 低”定向
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v; // 转为0索引
        if (h[u] > h[v]) {
            g[u].push_back(v);
        } else if (h[v] > h[u]) {
            g[v].push_back(u);
        }
        // 如果高度相等，不建边（不满足严格下降）
    }

    // 将节点按海拔从小到大排序（等高的相对顺序无所谓）
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    stable_sort(order.begin(), order.end(), [&](int a, int b){
        if (h[a] != h[b]) return h[a] < h[b];
        return a < b;
    });

    // dp[u]：从u出发的最长严格下降路径包含的景点数量
    vector<int> dp(n, 1);

    // 按海拔从小到大转移：u的出边指向更低海拔v，v已先被处理
    for (int u : order) {
        for (int v : g[u]) {
            dp[u] = max(dp[u], 1 + dp[v]);
        }
    }

    // 取全局最大
    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, dp[i]);
    cout << ans << "\n";
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    h = [int(next(it)) for _ in range(n)]

    # 邻接表：将无向边按“高 -> 低”定向
    g = [[] for _ in range(n)]
    for _ in range(m):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        if h[u] > h[v]:
            g[u].append(v)
        elif h[v] > h[u]:
            g[v].append(u)
        # 等高不建边

    # 按海拔从小到大排序（等高无所谓）
    order = list(range(n))
    order.sort(key=lambda x: (h[x], x))

    # dp[u]：从u出发的最长严格下降路径包含的景点数量
    dp = [1] * n

    # 转移：u的出边必指向更低海拔v，v已先被处理
    for u in order:
        for v in g[u]:
            if dp[v] + 1 > dp[u]:
                dp[u] = dp[v] + 1

    print(max(dp))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        BufferedInputStream in;
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = new BufferedInputStream(is); }
        int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && c <= ' ') {}
            if (c == -1) return null;
            do {
                sb.append((char)c);
                c = read();
            } while (c != -1 && c > ' ');
            return sb.toString();
        }
        int nextInt() throws IOException { return Integer.parseInt(next()); }
        long nextLong() throws IOException { return Long.parseLong(next()); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        String tok = fs.next();
        if (tok == null) return;
        int n = Integer.parseInt(tok);
        int m = fs.nextInt();

        long[] h = new long[n];
        for (int i = 0; i < n; i++) h[i] = fs.nextLong();

        // 邻接表：将无向边按“高 -> 低”定向
        ArrayList<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = fs.nextInt() - 1, v = fs.nextInt() - 1;
            if (h[u] > h[v]) g[u].add(v);
            else if (h[v] > h[u]) g[v].add(u);
            // 等高不建边
        }

        // 按海拔从小到大排序（等高顺序无所谓）
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> {
            if (h[a] != h[b]) return Long.compare(h[a], h[b]);
            return Integer.compare(a, b);
        });

        // dp[u]：从u出发的最长严格下降路径包含的景点数量
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        // 转移：u的出边必指向更低海拔v，v已先被处理
        for (int u : order) {
            for (int v : g[u]) {
                dp[u] = Math.max(dp[u], 1 + dp[v]);
            }
        }

        int ans = 0;
        for (int x : dp) ans = Math.max(ans, x);
        System.out.println(ans);
    }
}

题目内容

爱旅游的老张来到了我国西南地区的某个城市旅游。这个城市以海拔落差大著称，同一个城市内既能领略雪山的伟岸，又能欣赏平原溪流的静谧。老张提前在网上做好了攻略，掌握了这个城市所有的景点间的通行路线以及各个景点的海拔高度信息。

老张计划从自己规划的起点出发，一直走到自己规划的终点。由于走上坡路段会耗费大量体力，上了年纪的老张希望游览的过程中都是向下走，即如果他规划的游览景点路线为 $a_1,a_2,..a_1...a_k$ ，则对于每个 $1≤i<k$ ，都有 $h[a_i]>h[a_{i+1}]$ 。老张希望在满足上述条件下尽可能多的游览景点，请你帮他规划线路并给出最多可以游览的最点数量。

输入描述

第一行两个正整数 $n$ 和 $m$ ，表示景点数量以及可以通行的景点路线数量。

第二行 $n$ 个整数 $h_1,…,h_n$ ，分别表示第 $1$ 到 $n$ 个景点的海拔高度。

接下来 $m$ 行，每行两个整数 $u,v$，表示存在一条可以双向通行的路线使得景点 $u$ 与 $v$ 之间互相可以直达。

$1≤n,m≤10^5，0≤h_i≤10^9,1≤u,v≤n$ ，数据可能存在重边或自环。

输出描述

一个整数，表示在满足条件下老张最多可以游览的景点数量。

样例1

输入

5 4
4 2 4 5 8
1 2
2 3
3 4
5 4

输出

4

说明

其中一种可行的规划线路为 $5->4->3->2$ ，海拔高度依次为 $8,5,4,2$ 。是满足要求的情况下游览景点最多的，最大游览数量为 $4$ 。

样例2

输入

3 3
2 4 6
1 2
2 3
3 1

输出

3

说明

景点两两间的路径是双向的，结合海拔高度的要求，最终规划路线为 $3->2->1$ ，最大游览数量为 $3$ 。