算法题：滑雪

问题描述

我那年去瑞士滑雪，一下飞机，头一口气就呛晕了，空气太纯，醉氧!幸好赶来的医生让我闻了几下汽车尾气才缓过来……”楚继光心有余悸地说。

楚继光喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当楚继光滑到坡底，不得不再次走上坡或等着直升机来载他，楚继光想知道在一个区域中最长的滑坡，滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。

样例：

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

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

输入格式

输入要求：第一行为表示区域的二维数组的行数R和列数C（1≤R,C≤100），下面是R行，每行有C个数代表高度。

输出格式

最长滑坡长度。如上个样例的结果是25。

样例

输入

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

输出

25

解决方案

思路

记忆化搜索

代码

#include <iostream>

using namespace std;

const int N = 105;

int r, c;
int arr[N][N];
int dp[N][N];

int dfs(int x, int y) {
    if (dp[x][y])
        return dp[x][y];

    int offset_x[] = {1, -1, 0, 0};
    int offset_y[] = {0, 0, 1, -1};

    for (int i = 0; i < 4; ++i) {
        int tx = x + offset_x[i];
        int ty = y + offset_y[i];
        if (tx >= 0 && tx < r && ty >= 0 && ty < c && arr[x][y] > arr[tx][ty]) {
            int t = dfs(tx, ty) + 1;
            if (t > dp[x][y])
                dp[x][y] = t;
        }
    }

    return dp[x][y];
}

int main() {

    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> arr[i][j];
        }
    }

    int m = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            dp[i][j] = dfs(i, j);
            if (dp[i][j] > m)
                m = dp[i][j];
        }
    }

    cout << m + 1;
    return 0;
}