[SHOI2002] 滑雪

形式化题目

给定一个 $R$ 行 $C$ 列的矩阵，每个格子有一个整数高度 $h$ 。

从任意格子出发，每次可以滑到上下左右相邻、且高度严格更小的格子，可以滑任意多次。

求一条经过格子数最多的合法路线，输出其长度。

思路

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-17 13:04
 * update_at: 2026-08-17 13:10
 */
// brute.cpp：小数据暴力解，把每一步的移动方向看成选择序列来递归枚举所有滑坡路线。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

int R, C;
int h[maxn][maxn];   // h[i][j] 格子 (i,j) 的高度
int ans = 1;         // 最长滑坡长度

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

// 当前停在 (x,y)，这条路线已经经过 len 个格子。
// 这一层要做选择：从上下左右四个方向里挑一个还没越界且高度严格更小的方向继续滑。
// 高度严格递减保证路线不会绕回走重复格子，所以不需要记录访问状态。
void dfs(int x, int y, int len) {
    if (ans < len) ans = len;   // 无论继续与否，当前都是一条完整路线，更新答案
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] >= h[x][y]) continue;   // 只能滑到高度严格更小的格子
        dfs(nx, ny, len + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            cin >> h[i][j];

    // 从每个格子出发各枚举一次所有路线，取最长的那条。
    // 路线数量随格子数指数增长，只适合小数据对拍。
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            dfs(i, j, 1);

    cout << ans << endl;
    return 0;
}

这个暴力把每条路线看成一串「选择」：每层递归停在某个格子，选择上下左右中一个合法方向继续滑。它枚举了所有可能的路线，但同一个格子会被多条路线的后半段反复走到，路线数量随格子数指数增长，只适合小数据。

关键观察：高度严格递减。沿路线高度一路变小，所以路线永远不会绕圈（无环）；同时「从格子 $(i,j)$ 出发的最长长度」是一个只由自己决定的固定值，与前面怎么滑到它无关。

于是定义状态：

f[i][j] = \text{从格子 }(i,j)\text{ 出发能滑出的最长长度}

转移：第一步只能滑向高度更小的相邻格子，选其中 $f$ 值最大者，再算上本格：

f[i][j] = 1 + \max\{\, f[nx][ny] \mid (nx,ny) \text{ 与 } (i,j) \text{ 相邻且 } h[nx][ny] < h[i][j] \,\}

答案就是所有 $f[i][j]$ 的最大值。

用记忆化搜索实现：dfs(i,j) 算过就直接返回缓存值，否则枚举四个方向递归计算。与暴力相比只多了一张「算过就不再算」的表，但每个格子恰好只算一次，复杂度降到 $O(RC)$ 。

DP 表格

这张表展示一个小规模构造样例（3x3）的高度网格和对应的 $f$ 值：

text

从每个格子出发的最长滑坡长度 $f[i][j]$ ：

i \ j	1	2	3
1	2	1	2
2	3	4	3
3	4	5	6

单元格 $f[i][j]$ 表示从第 $i$ 行第 $j$ 列的格子出发能滑出的最长长度。

看 $h=9$ （右下角）这一格的转移：它的四个邻居中更低的是 $5$ （ $f=3$ ）和 $8$ （ $f=5$ ），所以 $f[3][3] = 1 + \max(3, 5) = 6$ ，对应路线 $9 \to 8 \to 6 \to 4 \to 2 \to 1$ 。整张表的答案就是所有 $f$ 的最大值 $6$ 。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-17 13:04
 * update_at: 2026-08-17 13:10
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

int R, C;
int h[maxn][maxn];     // h[i][j] 格子 (i,j) 的高度
int f[maxn][maxn];     // f[i][j] 从 (i,j) 出发的最长滑坡长度，-1 表示还没计算

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

// 计算从 (x,y) 出发能滑出的最长长度（记忆化搜索）
int dfs(int x, int y) {
    if (f[x][y] != -1) return f[x][y];
    int res = 1;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] >= h[x][y]) continue;   // 只能滑到高度严格更小的格子
        res = max(res, dfs(nx, ny) + 1);
    }
    return f[x][y] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            cin >> h[i][j];

    memset(f, -1, sizeof(f));

    int ans = 0;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            ans = max(ans, dfs(i, j));

    cout << ans << endl;
    return 0;
}

vis 数组版写法

上面 main.cpp 用 f[i][j] = -1 表示「还没算过」；这一版改用单独的 vis 数组来标记： f[i][j] 在读入时就全部初始化为 $1$ （每个格子至少能停在本格），dfs 进入时先查 vis 是否算过，算完后用 f[i][j] = max + 1 更新。两种写法表达的记忆化搜索完全相同。

cpp

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
67
68
69
70
71
72
73
74
75
76
77/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-17 14:42
 * update_at: 2026-08-17 14:42
 */
/*============================================================================
* Title : tvoj 1004 滑雪
* Author: Rainboy
* Time  : 2016-05-03 17:44
* update: 2016-05-03 17:44
* © Copyright 2016 Rainboy. All Rights Reserved.
*=============================================================================*/


#include <cstdio>

#define N 110       //定义最大量

/* 数据存储 */
int r,c;
int ha[N][N];//滑雪场的大小
int f[N][N];//记录某个点开始滑雪的最大值
bool vis[N][N]={0};//有没有访问过

int dir[4][2]  = {{-1,0},{1,0},{0,-1},{0,1}}; //四个方向

/* 判断i,j是否在范围内 */
bool judge(int i,int j){
    if(i >=1 && i<= r && j>=1 && j<=c)
        return true;
    return false;
}

int dfs(int i,int j){
    if( vis[i][j] != 0) return f[i][j]; //已经访问过,返回
    vis[i][j] =1;   //设置已经访问过
    int ii,ij;
    int max =-1,tmp;
    int k;
    for (k=0;k<4;k++){ //访问周围的4个点
        ii=i+dir[k][0],ij=j+dir[k][1];
        /* 点在范围内 且 能到达 */
        if( judge(ii,ij) && ha[ii][ij] < ha[i][j]){
            tmp = dfs(ii,ij);
            if(max<=tmp)
                max=tmp;
        }
    }
    if(f[i][j] < max+1) //更新
        f[i][j] = max+1;
    return f[i][j];
}

int main(){
    int i,j;
    /* 数据读取 */
    scanf("%d%d",&r,&c);
    for (i=1;i<=r;i++){
        for (j=1;j<=c;j++){
            scanf("%d",&ha[i][j]);
            f[i][j]=1;
        }
    }

    int max=0,tmp;
    for (i=1;i<=r;i++){ //尝试所有点
        for (j=1;j<=c;j++){
            tmp = dfs(i,j);
            if( max < tmp)
                max = tmp;
        }
    }
    printf("%d",max);
    return 0;
}

注意这版代码里如果某个格子没有更低的邻居，max 保持为 $-1$ ，f[i][j] < max + 1 不成立， f[i][j] 仍然是初始值 $1$ ，正好对应「只滑本格」的情况。

复杂度

每个格子至多计算一次，每次枚举 $4$ 个方向，时间复杂度 $O(RC)$ ，空间复杂度 $O(RC)$ 。

总结

「高度严格递减」是这题的题眼：它同时给出无环（递归必然终止）和最优子结构（答案只由更低的邻居决定）两个保证。把网格当成 DAG 做最长路，记忆化搜索是让暴力枚举不重复计算的最小改动，也是这类「递归式已写出、只差缓存」问题的标准套路。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6R x C 网格，只能滑向高度严格更小的相邻格
|- 观察 1：严格递减 -> 路线无环，本质是 DAG 最长路
|- 观察 2：同一格子的后半段会被多条路线重复走
`- 记忆化：f[i][j] = 1 + max(f[更低邻居])
   `- 每个格子只算一次，O(R*C)
      `- 答案 = max f[i][j]

先看每个节点对应的推理结论：无环保证递归终止，重复计算暴露了朴素枚举的瓶颈，而「格子的答案只由更低的邻居决定」提供了递推式。顺着分支往下，每一步都只是把上一步的结论再推进一层，最终落到 $O(RC)$ 的记忆化搜索。

目录

形式化题目

思路

DP 表格

代码

vis 数组版写法

复杂度

总结

图示解析