Table of Contents
- 前言：
- Problem C：P1434 [SHOI2002] 滑雪
- 结语：
Powered by GhostFace's Emacs.
前言：
Ctorch诞生的第179天，小小的庆祝一下。
再次宣传我们团队的项目：https://github.com/ShengFlow/CTorch/tree/feature-nn.Module
这是一个纯C++写的高性能ML库，我们将会在2026.2.16（除夕夜24:00）发布第一个内测版本（RC 1），敬请期待。
这是一次比赛的赛后补题记录&题解（Part 2）。
本文由 Emacs 29.0 Org-mode 写成，在此感谢GNU做出的开源软件运动。
Problem C：P1434 [SHOI2002] 滑雪
这道题是我认为非常有价值的一道题目，它的价值不在于思维复杂，而是提供了一个「搜索与动态规划之间的桥梁」。
它告诉我们：“记忆化搜索就是动态规划的一种实现方式”，换言之，记忆化搜索与动态规划是「一体两面」的关系，任何动态规划都可以写成记忆化搜索。
我们后文会阐述这一点。
题目大意：
给定一个矩阵，寻找矩阵中的一条最长下降路径。
WriteUp：
这道题目在一本通·提高篇里仍然有。
这道题很明显应该使用搜索解决，然而，当你把一个裸的dfs提交上去时，你就会发现，这道题TLE了。
原因是什么呢？我们重复搜索了太多的点（或者说：「解空间」）。
那么怎么解决这个问题呢，我们考虑一下，是否在任意时刻，我们搜索到矩阵中 点 \(A_{i,j}\) 时，其结果都是一样的？
答案是显然的，对于任何一个点，从这个点出发的「最长下降路径长度」始终不变。
那么对于同一个点，我们就没必要在同样的结果上花费时间进行搜索。
由此，我们可以使用一个数组 \(memo\) 存储搜索过的结果，其中 \(memo_{i,j}\) 代表从 \(A_{i,j}\) 出发的「最长下降路径长度」。
正如我们一开始所说，“记忆化搜索和动态规划是一体两面的关系”，对于这道题，我们就有两种方法解决，它们是等价的。
一、记忆化搜索
如上文所述，我们需要改造一下dfs主函数，使其返回一个 \(int\) 型的值，代表从 \(A_{i,j}\) 出发的「最长下降路径长度」。
随后，在每次搜索之前，我们需要检查一下 \(memo\) 数组中是否存在结果，如果存在，直接返回，不再搜索。
这个套路是通用的，当我们发现问题的 「重叠子问题」 时，我们就可以使用记忆化搜索。
代码如下：
[code]#include using namespace std;static const int MAXN = 105;static int height[MAXN][MAXN];static int memo[MAXN][MAXN]; static int n, m;static const int dx[] = {0, 0, 1, -1};static const int dy[] = {1, -1, 0, 0};// 自顶向下的记忆化搜索static int dfs(int x, int y) { int& res = memo[x][y]; // 这里使用了引用，即“&”，它不会拷贝变量，更省内存，尤其是在使用vector这种容器时，拷贝会极其费时费力。 if (res != -1) return res; // 已计算过则直接返回 res = 1; // 至少包含当前节点 for (int dir = 0; dir < 4; ++dir) { const int nx = x + dx[dir]; const int ny = y + dy[dir]; // 越界检查 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 只能向更低处移动 if (height[x][y] > n >> m)) return 0; for (int i = 1; i height[j]; } } // 初始化 memo 为 -1 表示未访问 memset(memo, -1, sizeof(memo)); int answer = 0; for (int i = 1; i > n >> m)) return 0; priority_queue pq; for (int i = 1; i height[j]; dp[j] = 1; // 初始状态：至少包含自身 pq.push({i, j, height[j]}); } } int answer = 0; while (!pq.empty()) { auto [x, y, cur_h] = pq.top(); pq.pop(); const int current_dp = dp[x][y]; answer = max(answer, current_dp); // 尝试向四个方向扩展（从低到高处理，所以是反向传播） const int dx[] = {-1, 1, 0, 0}; // 上下左右 const int dy[] = {0, 0, -1, 1}; for (int dir = 0; dir < 4; ++dir) { const int nx = x + dx[dir]; const int ny = y + dy[dir]; // 越界检查 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 只能从更高的邻居转移过来（反向思考：当前点更新其高处邻居） if (height[nx][ny] |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
