原题链接

题目描述

​ Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

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

​ 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24－17－16－1$（从 $24$ 开始，在 $1$ 结束）。当然 $25－24－23－\ldots－3－2－1$ 更长。事实上，这是最长的一条。

输入输出格式

输入格式

输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

输入1 :

5 5
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

输出1 :

25

说明

对于 $100\%$ 的数据，$1\leq R,C\leq 100$。

40分做法（裸dfs）

​ 从每个点出发搜一遍，统计最大值。

#include <bits/stdc++.h>
using namespace std;
int n, m, e[105][105], ans;
const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
void dfs(int x, int y, int len) {
    ans = max(len, ans);
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || yy < 1 || xx > n || yy > m || e[xx][yy] > e[x][y])
            continue;
        dfs(xx, yy, len + 1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> e[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j, 1);
        }
    }
    cout << ans;
    return 0;
}

50分做法（加错误的记忆化）

​ 加入一个错误的记忆化，居然加了10分

#include <bits/stdc++.h>
using namespace std;
int n, m, e[105][105], ans, p[105][105];
const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
int dfs(int x, int y) {
    if (p[x][y] > 0)
        return p[x][y];  // update
    int maxn = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || yy < 1 || xx > n || yy > m || e[xx][yy] > e[x][y])
            continue;
        maxn = max(maxn, dfs(xx, yy) + 1);
    }
    return p[x][y] = maxn;  // update
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> e[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(dfs(i, j), ans);
        }
    }
    cout << ans;
    return 0;
}

100分做法（正确的记忆化）

​ 在原先基础上改进一下 e[xx][yy]>e[x][y] 改为 e[xx][yy]>=e[x][y] AC 。

#include <bits/stdc++.h>
using namespace std;
int n, m, e[105][105], ans, p[105][105];
const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
int dfs(int x, int y) {
    if (p[x][y] > 0)
        return p[x][y];
    int maxn = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || yy < 1 || xx > n || yy > m || e[xx][yy] >= e[x][y])
            continue;
        maxn = max(maxn, dfs(xx, yy) + 1);
    }
    return p[x][y] = maxn;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> e[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(dfs(i, j), ans);
        }
    }
    cout << ans;
    return 0;
}

​ 记忆化原理，搜到一个搜过的点，如果可以下一步到这个点，直接返回该点的长度，这样两条长度就能拼在一起了。

感谢

​ 本文的创作过程受到了嘉持的视频的启发，特此感谢。