洛谷P1434《[SHOI2010]滑雪》

一月 27, 2019 2565

记忆化搜索好题

题目描述

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

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

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例

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

解题思路

一眼就能看出这是搜索题

方法很显然，枚举所有的点，从当前点开始 DFS，每次往四个方向搜索，直到不能搜为止，这时候答案就出来了一个，更新一下。

考虑一下优化。
在每次搜索的过程中，我们有很多点是重复走过的，那么就可以把暴搜升级为记忆化搜索。
用 \text{mem}(x,y) 表示从点 (x,y) 出发的最长路径，在每一次搜索完成之后更新一下当前的答案，记录到 \text{mem}(x,y) 中即可。等到下一次搜到这个点（记为 (x',y') ），如果 \text{mem}(x',y') \geq 0 （也就是被更新过了），直接返回 \text{mem}(x',y') 就行。

我们也可以把记忆化搜索升级为 DP 不过据说比记忆化搜索还慢
DP 做法题解已提上日程。

代码实现

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
#include <iostream>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int dx[] = { 0,  0, -1,  1 };
const int dy[] = { 1, -1,  0,  0 };
const int MAXRC = 100 + 10;

int snow[MAXRC][MAXRC];
int r, c, ans;
int mem[MAXRC][MAXRC];

int Search(int x, int y) {
    int t = 1;
    if (mem[x][y]) t = mem[x][y];
    else {
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > 0 && ny > 0 && nx <= r && ny <= c && snow[x][y] < snow[nx][ny]) {
                t = std::max(t, Search(nx, ny) + 1);
            }
        }
    }
    mem[x][y] = t;
    return t;
}

int main() {
    IMPROVE_IO();
    cin >> r >> c;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            cin >> snow[i][j];
        }
    }
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            int now = Search(i, j);
            mem[i][j] = now;
            ans = std::max(ans, mem[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}