读题
P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给定一个含有海拔高度的矩形，算出从高到低“滑雪”的最大长度。
“滑雪”只能从一个格子滑到上下左右相邻，且海拔严格小于当前海拔的格子。
例如：
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
|
这里的最大路径是：
![Clip_2024-05-28_21-12-10]()
共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代码
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)
{
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;
}
}
cin >> r >> c;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> block[i][j];
}
}
int ans = 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;
}
|
