**ACM 历年真题查找与经典题目解析**
一、ACM 历年真题查找
ACM 历年真题的查找，可以通过多个在线平台获取，如 ACM 官网、ICPC Live Archive、OJ
（在线判题系统）等。其中，ICPC Live Archive 存档了从 1990 年到 2017 年的 ACM ICPC 区域
赛和总决赛的题目，而 OJ 如 Codeforces、Vjudge 等也提供了大量的 ACM 相关题目。
二、经典真题解析
以下选取**2018 年 ACM 国际大学生程序设计竞赛的一道真题**“Skiing”进行解析和讲解。
本题主要考察图论中的最短路径问题，以及动态规划或递归的解题思路。
### 题目描述
给定一个二维的滑雪场地，每个位置的高度由一个整数表示。滑雪者可以从一个位置滑到相
邻的四个方向（上、下、左、右）的任一位置，只要那个位置的高度比当前位置低。滑雪者
想要找到从给定的起点到终点的最长滑雪路径的长度。
### 解析与讲解
#### 1. 问题分析
* **核心考点**：本题主要考察图论中的最短路径问题，但在这里我们需要找到的是最长路
径。
* **解题思路**：由于滑雪者只能滑向高度更低的位置，因此本题实际上是一个求最长下降
路径的问题。我们可以使用动态规划或递归的方法来解决。
#### 2. 动态规划或递归思路
* **定义状态**：设`dp[i][j]`表示从位置`(i, j)`到终点的最长滑雪路径长度。
* **状态转移**：对于每个位置`(i, j)`，我们需要考虑其四个相邻位置（如果它们存在且高度
更低），并选择其中最长的一条路径作为`dp[i][j]`的值。即`dp[i][j] = max(dp[i-1][j], dp[i+1][j],
dp[i][j-1], dp[i][j+1]) + 1`（如果相邻位置存在且高度更低）。
* **边界条件**：对于终点位置，其最长滑雪路径长度为 0，即`dp[end_i][end_j] = 0`。
* **计算顺序**：从终点开始，逐步向前计算每个位置的最长滑雪路径长度。
#### 3. 实现步骤
1. **输入处理**：读取滑雪场地的高度图、起点和终点的位置。
2. **初始化**：将`dp`数组初始化为一个较小的值（如-1），表示当前位置无法到达终点。
3. **动态规划或递归计算**：从终点开始，逐步向前计算每个位置的最长滑雪路径长度。
4. **输出结果**：输出起点位置的最长滑雪路径长度。
