补题日记：26-1-13

Table of Contents

• 前言：
  
• Problem C：P1434 [SHOI2002] 滑雪
  
  
  • 标题大意：
    
  • 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 [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]