Vijos 1011 清帝之惑之顺治记忆录式的动态规划（记忆化搜索）

背景

顺治帝福临，是清朝入关后的第一位皇帝。他是皇太极的第九子，生于崇德三年（1638）崇德八年八月二ten+six日在沈阳即位，改元顺治，在位18年。卒于顺治十八年（1661），终24岁。

顺治即位后，由叔父多尔衮辅政。顺治七年，多尔衮出塞射猎，死于塞外。14岁的福临提前亲政。顺治帝天资聪颖，读书勤奋，他吸收先进的汉文化，审时度势，对成法祖制有所更张，且不顾满洲亲贵大臣的反对，倚重汉官。为了使新兴的统治基业长治久安，他以明之兴亡为借鉴，警惕宦官朋党为祸，重视整饬吏治，注意与民休息，取之有节。但他少年气盛，刚愎自用，急噪易怒，当他宠爱的董妃去世后，转而消极厌世，终于匆匆走完短暂的人生历程，英年早逝。他是清朝历史上唯一公开归依禅门的皇帝。

描述

顺治喜欢滑雪，这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待太监们来载你。顺治想知道载一个区域中最长的滑坡。

区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

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。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

格式

输入格式

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 500)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

输出格式

输出最长区域的长度。

样例1

样例输入1

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

题解

这道题目是一道动态规划题，可以使用记忆录式的动态规划（也成为记忆化搜索）。

代码：

#include <iostream>

using namespace std;

int n, m, f[550][550], h[550][550], ans = 0;

int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

bool inMap(int x, int y)

{

    return x >= 0 && x < n && y >= 0 && y < m;

}

int dfs(int x, int y)

{

    if (f[x][y])

        return f[x][y];

    f[x][y] = 1;

    for (int i = 0; i < 4; i ++)

    {

        int xx = x + dir[i][0];

        int yy = y + dir[i][1];

        if (inMap(xx, yy) && h[xx][yy] > h[x][y]) {

            f[x][y] = max(f[x][y], dfs(xx, yy) + 1);

        }

    }

    return f[x][y];

}

int main()

{

    cin >> n >> m;

    for (int i = 0; i < n; i ++)

        for (int j = 0; j < m; j ++)

            cin >> h[i][j];

    for (int i = 0; i < n; i ++)

        for (int j = 0; j < m; j ++)

            if (dfs(i, j) > ans)

                ans = dfs(i, j);

    cout << ans << endl;

    return 0;

}

巴特西

Vijos 1011 清帝之惑之顺治记忆录式的动态规划（记忆化搜索）

背景

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

题解

最新文章

热门文章

巴特西

Vijos 1011 清帝之惑之顺治 记忆录式的动态规划（记忆化搜索）

背景

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

题解

最新文章

热门文章

Vijos 1011 清帝之惑之顺治记忆录式的动态规划（记忆化搜索）