题目简述

www.luogu.com.cn

给出一个 n×mn \times m 的二维数组，求出最长的一条滑坡，使得这条滑坡的高度会依次减少。

解题思路

原始DFS

这是一道 DFS\text{DFS} 搜索题，同样也可以使用 DP\text{DP} 来做。

这里用DFS。

可以先双重循环这个二维数组上的每个点，在每个点上进行周围四个点的搜索（同时也要注意边界条件）。

可以设定两个偏移数组如下。

1
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dfs(int x, int y)
{
    if (s[x][y])
        return s[x][y];
    s[x][y] = 1;
    for (int i = 0; i <= 3; i++)
    {
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if (xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy])
        {
            dfs(xx, yy);
            s[x][y] = max(s[x][y], s[xx][yy] + 1);
        }
    }
    return s[x][y];
}

即便 m,nm,n 两个最大值为 100100，暴力DFS仍然会超时。

因此我们需要采用记忆化搜索。

记忆化搜索（优化）

首先在建立一个数组s，si,js_{i,j}表示坐标 (i,j)(i,j) 点上的最优值，在搜索这个点的周围点时，如果有 si+dxk,j+dyks_{i+dx_{k},j+dy_{k}} 的值小于 si,js_{i,j}，则直接return掉从而进入下次搜索。

从而可以大幅度的降低时间复杂度。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m;
int a[N][N], s[N][N], ans;

int dfs(int x, int y)
{
    if (s[x][y])
        return s[x][y];
    s[x][y] = 1;
    for (int i = 0; i <= 3; i++)
    {
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if (xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy])
        {
            dfs(xx, yy);
            s[x][y] = max(s[x][y], s[xx][yy] + 1);
        }
    }
    return s[x][y];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= m; j++)
            ans = max(ans, dfs(i, j));
    cout << ans << endl;
    return 0;
}