补题日记：26-1-13
Table of Contents[*]前言：
[*]Problem C：P1434 滑雪
[*]题目大意：
[*]WriteUp：
[*]一、记忆化搜索
[*]二、动态规划
[*]总结：
[*]结语：
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 滑雪
这道题是我认为非常有价值的一道题目，它的价值不在于思维复杂，而是提供了一个「搜索与动态规划之间的桥梁」。
它告诉我们：“记忆化搜索就是动态规划的一种实现方式”，换言之，记忆化搜索与动态规划是「一体两面」的关系，任何动态规划都可以写成记忆化搜索。
我们后文会阐述这一点。
题目大意：
给定一个矩阵，寻找矩阵中的一条最长下降路径。
WriteUp：
这道题目在一本通·提高篇里仍然有。
这道题很明显应该使用搜索解决，然而，当你把一个裸的dfs提交上去时，你就会发现，这道题TLE了。
原因是什么呢？我们重复搜索了太多的点（或者说：「解空间」）。
那么怎么解决这个问题呢，我们考虑一下，是否在任意时刻，我们搜索到矩阵中 点 \(A_{i,j}\) 时，其结果都是一样的？
答案是显然的，对于任何一个点，从这个点出发的「最长下降路径长度」始终不变。
那么对于同一个点，我们就没必要在同样的结果上花费时间进行搜索。
由此，我们可以使用一个数组 \(memo\) 存储搜索过的结果，其中 \(memo_{i,j}\) 代表从 \(A_{i,j}\) 出发的「最长下降路径长度」。
正如我们一开始所说，“记忆化搜索和动态规划是一体两面的关系”，对于这道题，我们就有两种方法解决，它们是等价的。
一、记忆化搜索
如上文所述，我们需要改造一下dfs主函数，使其返回一个 \(int\) 型的值，代表从 \(A_{i,j}\) 出发的「最长下降路径长度」。
随后，在每次搜索之前，我们需要检查一下 \(memo\) 数组中是否存在结果，如果存在，直接返回，不再搜索。
这个套路是通用的，当我们发现问题的 「重叠子问题」 时，我们就可以使用记忆化搜索。
代码如下：
#include using namespace std;static const int MAXN = 105;static int height;static int memo;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; // 这里使用了引用，即“&”，它不会拷贝变量，更省内存，尤其是在使用vector这种容器时，拷贝会极其费时费力。 if (res != -1) return res;// 已计算过则直接返回 res = 1;// 至少包含当前节点 for (int dir = 0; dir < 4; ++dir) { const int nx = x + dx; const int ny = y + dy; // 越界检查 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 只能向更低处移动 if (height > n >> m)) return 0; for (int i = 1; iheight; } } // 初始化 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; iheight; dp = 1;// 初始状态：至少包含自身 pq.push({i, j, height}); } } int answer = 0; while (!pq.empty()) { auto = pq.top(); pq.pop(); const int current_dp = dp; 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; const int ny = y + dy; // 越界检查 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 只能从更高的邻居转移过来（反向思考：当前点更新其高处邻居） if (height 东西不错很实用谢谢分享 热心回复！ 东西不错很实用谢谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 谢谢楼主提供！ 过来提前占个楼 感谢分享 收藏一下 不知道什么时候能用到 过来提前占个楼 感谢发布原创作品，程序园因你更精彩 不错，里面软件多更新就更好了 热心回复！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢分享，学习下。 yyds。多谢分享 过来提前占个楼 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 这个好，看起来很实用
页:
[1]
2