滑雪——记忆化搜索（C++）

不要忘记拍摄美照，留下珍贵的滑雪记忆 #生活乐趣# #旅行建议# #滑雪旅游#

AcWing 901. 滑雪
给定一个R行C列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

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 123456789

在给定矩阵中，一条可行的滑行轨迹为24-17-2-1。

在给定矩阵中，最长的滑行轨迹为25-24-23-…-3-2-1，沿途共经过25个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式
第一行包含两个整数R和C。

接下来R行，每行包含C个整数，表示完整的二维矩阵。

输出格式
输出一个整数，表示可完成的最长滑雪长度。

数据范围
1≤R,C≤300,
0≤矩阵中整数≤10000
输入样例：

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 123456

输出样例：

25 1

注意：f[][]二维数组初始化的时候最好统一赋值为-1，如果不进行初始化直接用0判断，此题可以，可是如果遇到一些记忆化搜索的问题要求方案数的时候，初始化是0可能会导致个别情况计算出来的恰好结果是0时，却被认为未遍历过，因此统一赋值为-1就没错了

#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 310; int n, m; int g[N][N]; int f[N][N]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int dp(int x, int y) { int &v = f[x][y]; if (v != -1) return v; v = 1; for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]) v = max(v, dp(a, b) + 1); } return v; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &g[i][j]); memset(f, -1, sizeof f); int res = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) res = max(res, dp(i, j)); printf("%d\n", res); return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849

网址：滑雪——记忆化搜索（C++） https://www.yuejiaxmz.com/news/view/440722

相关内容

滑雪风靡？“体验式滑雪”和“末路式捞金”
在最热滑雪季“穷滑”，如何以最低成本获得最多的滑雪乐趣？
“北雪南移”成为滑雪市场新趋势
11月开板迎最热滑雪季 “一起滑雪”成流行趋势
动态规划特训：旅行商问题（回溯法或记忆搜索法）
最热冰雪季已来“滑雪+运动”成流行生活方式
夏天滑雪成为新的生活方式 尽享滑雪的乐趣
重温热搜，忆起无数个关于陪伴的瞬间——《2022年轻人数字生活白皮书》
在雪中畅滑，感受冬日的快乐与奇妙
最热冰雪季已来 “滑雪+运动”成流行生活方式

随便看看