AcWing 901. 滑雪
原题链接
简单
作者:
浅笙yax
,
2024-04-07 20:53:23
,
所有人可见
,
阅读 1
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*
(1)如果把int &v = f[x][y];去掉,原来所有 v 的位置写成f[x][y],效果是完全一样的.
引用只是给变量起了个小名,达到简化代码、便于书写的作用
(2)在记忆化搜索的代码中,起到关键作用的是记忆化数组f[i][j]。
如果只是采用 dfs 暴搜的话,每次在一个位置搜索完之后,状态都不会被保留,下次 dfs 还是重新开始,就会有很多被算过的位置再重新计算,数据量大就会超时;
记忆化搜索就是 dfs + 记忆化数组f[i][j],在算某一个位置时把它的所有路径上 所有算过的位置状态保存在数组f[i][j]里。
if (f[x][y] != -1) return f[x][y];下次求某个被算过的位置的状态时,无需重新计算,直接返回。是数组f[i][j]起到了记忆的作用。
这里面也体现了空间换时间的思想。
*/
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)
{
if (f[x][y] != -1) return f[x][y];
f[x][y] = 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])
f[x][y] = max(f[x][y], dp(a, b) + 1);
}
return f[x][y];
}
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;
}