读题

P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给定一个含有海拔高度的矩形，算出从高到低“滑雪”的最大长度。

“滑雪”只能从一个格子滑到上下左右相邻，且海拔严格小于当前海拔的格子。

例如：

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

这里的最大路径是：

共25格。

注意，“长度”为首尾经过总的格子的个数，比如路径$1\rightarrow 2$的长度为2。

题目给出的最大矩形长宽为100，记长为c(olumns)，宽为r(ows)

思路

第一想到的就是DFS（深度有限搜索），dfs(int x, int y)返回从[x][y]出发的最大长度。搜索的逻辑比较简单，就是寻找四周临近的格子的长度的最大值，加上1就是当前格子的最大长度。

但是这道题最大长宽为100，如果一个个暴力搜索肯定会超时的，最大的时间复杂度可能是$O(r^2c^2)$。

我们可以在暴力搜索的基础上进行记忆化搜索，建立一个数组rec[x][y]用于存储从[x][y]出发的最长长度，如果后续搜索到四周的格子，需要查找[x][y]的长度的话，直接返回这个记录的值就好了，不必再进行递归。

这样优化以后的空间复杂度和时间复杂度均仅为$O(rc)$（因为每个格子最多只要计算一次），完全能过。

AC代码

#include <bits/stdc++.h>

using namespace std;

int block[110][110]{0};
int rec[110][110]{0};  // 记忆
int r, c;

inline bool is_valid(int x, int y)  // 在范围内
{
    return x >= 0 && x < r && y >= 0 && y < c;
}

int dfs(int x, int y)  // 返回从x, y出发的最大的值
{
    if (rec[x][y] >= 0) return rec[x][y];

    int res = 1;
    int max_next = 0;

    if (is_valid(x - 1, y) && block[x - 1][y] < block[x][y])
        max_next = max(dfs(x - 1, y), max_next);
    if (is_valid(x + 1, y) && block[x + 1][y] < block[x][y])
        max_next = max(dfs(x + 1, y), max_next);
    if (is_valid(x, y - 1) && block[x][y - 1] < block[x][y])
        max_next = max(dfs(x, y - 1), max_next);
    if (is_valid(x, y + 1) && block[x][y + 1] < block[x][y])
        max_next = max(dfs(x, y + 1), max_next);
    res += max_next;

    rec[x][y] = res;
    return res;
}

int main()
{
    for (int i = 0; i < 110; i++)
    {
        for (int j = 0; j < 110; j++)
        {
            rec[i][j] = -1;  // 初始化，-1为无记录
        }
    }

    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> block[i][j];
        }
    }

    int ans = 1;  // 至少为1
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans << endl;

    system("pause");
    return 0;
}