P1434 [SHOI2002] Skiing: A Classic Dynamic Programming Challenge

Understanding the Problem

P1434 [SHOI2002] Skiing - Luogu | Computer Science Education New Ecology (luogu.com.cn)

Given a rectangular grid with elevations, calculate the maximum length of a “ski” path from high to low.

A “ski” move can only go from one cell to a cell that is adjacent to it vertically or horizontally, and whose elevation is strictly lower than the current cell’s elevation.

For example:

1
2
3
4
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

The maximum path here is:

It has 25 cells in total.

Note that “length” is the total number of cells passed through from start to end; for example, a path $1\rightarrow 2$ has length 2.

The maximum rectangle size given in the problem is 100 by 100; let the length be c(olumns) and the width be r(ows).

Approach

The first thing that comes to mind is DFS (depth-first search). dfs(int x, int y) returns the maximum length starting from [x][y]. The search logic is simple: find the maximum length among the neighboring cells in four directions, then add 1 to get the maximum length for the current cell.

But the maximum dimensions in this problem are 100 by 100, so brute-forcing every cell would definitely time out; the worst-case time complexity could be $O(r^2c^2)$.

We can add memoization on top of the brute-force search. Create an array rec[x][y] to store the maximum length starting from [x][y]. If a later search reaches a neighboring cell and needs the length for [x][y], just return the recorded value instead of recursing again.

After this optimization, both the space complexity and time complexity are only $O(rc)$ (because each cell is computed at most once), so it passes easily.

AC Code

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#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;
}