题目

滑雪

可以动态规划，也可以记忆化搜索

思路

这里只记录动态规划方法，算法如下：

1. 定义一个二维 $dp$ 数组用于记录每个位置的最大路径长度；
2. 按高度从小到大遍历每个位置 $x$，更新 $dp$ 数组：依次判断位置 $x$ 上下左右的位置 $k_i$，如果位置 $x$ 的高度大于 $k_i$，则将 $dp$ 数组中位置 $x$ 的对应值更新为 $max(d{p}_x,d{p}_{k_i}+1)$。
3. 答案即为 $max(d{p}_i)$，即所有位置的路径长度的最大值

根据算法，然后做出相应的实现，具体见代码，需要注意的是按高度从小到大遍历位置，要先将所有位置存储下来并按高度排序。

代码

#include <stdio.h>
#include <stdlib.h>
#define N 105

typedef struct pos {
    int x, y, h;
} P;

const int TO[][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

int cmp(const void* a, const void* b) {
    P aa = *(P*)a;
    P bb = *(P*)b;
    if (aa.h == bb.h) {
        if (aa.x == bb.x) {
            return aa.y - bb.y;
        }
        return aa.x - bb.x;
    }
    return aa.h - bb.h;
}

int main(void) {
    int n = 0, m = 0, a[N][N], h[N][N];
    scanf("%d%d", &n, &m);
    P pos[n * m];
    int i = 0, j = 0, t = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
            h[i][j] = 1;  // 请注意初始时每个位置的长度都是 1
            t = i * m + j;
            pos[t].x = i;
            pos[t].y = j;
            pos[t].h = a[i][j];
        }
    }
    qsort(pos, n * m, sizeof(P), cmp);
    int tx = 0, ty = 0;
    t = 0;
    for (i = 1; i < n * m; i++) {
        // 外循环从 1 开始，因为最小的高度的长度就是 1，不用管
        for (j = 0; j < 4; j++) {
            // 内循环依次判断当前点的上下左右位置
            tx = pos[i].x + TO[j][0];
            ty = pos[i].y + TO[j][1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m &&
                pos[i].h > a[tx][ty]) {
                if (h[tx][ty] + 1 > h[pos[i].x][pos[i].y]) {
                    h[pos[i].x][pos[i].y] = h[tx][ty] + 1;
                    // 在计算每个点的路径长度的时候顺便记录最大值
                    if (h[pos[i].x][pos[i].y] > t) t = h[pos[i].x][pos[i].y];
                }
            }
        }
    }
    // 输出最大值即可
    printf("%d\n", t);
    return 0;
}