题目描述
给定一个 R 行 C 列的矩阵,表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。
当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
记忆化搜索 dfs + 数组保存
解题思路
可以用dp另一种实现方式记忆化搜索实现.
状态定义:
d[i][j]
集合:以(i,j)作为起点的所有滑动路径
属性:Max
状态划分
记忆化搜索与一般dp的思路相反.一般dp考虑的是当前状态的上一个状态;而记忆化搜索
是当前状态能到达哪些状态.一个是自底向上一个是自顶向下.
考虑(i,j)下一个能去哪:上下左右四个方向.以下一个位置在(x,y)为例.
确定部分:起点在(i,j);可变部分:以(x,y)为起点的所有路径的最大值,也就是d[x][y].
注意状态(x,y)可能是空集(不符合条件),(x,y)需要:
(x,y)在滑雪场内;
(x,y)的高度低于(i,j)
可以用dp的前提是状态图是一个有向无环图(拓扑图),也就是把每个状态作为一个结点,状态转移作为有向边构成
的图无环.因为有下一个状态存在的前提是高度更低作为保证,所以不可能有环.(a>b>c>a->a>a矛盾)
时间复杂度
状态数目 * 状态转移 = nm4 = O(nm)
C++ 代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max_N = 310;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};//偏移量
int n, m;
int h[Max_N][Max_N]; //高度
int d[Max_N][Max_N];//状态
int dp(int x, int y)
{
int &ans = d[x][y];
if( ans!=-1 ) return ans;//已经计算过
ans = 1;//初值为1
for( int i = 0; i<4; i++ )
{
int nx = x + dx[i], ny = y + dy[i];
if( 1<=nx&&nx<=n && 1<=ny&&ny<=m && h[x][y]>h[nx][ny] )
{
ans = max( ans, dp(nx,ny)+1 );
}
}
return ans;
}
int main()
{
cin >> n >> m;
for( int i = 1; i<=n; i++ )
{
for( int j = 1; j<=m; j++ )
cin >> h[i][j];
}
int res = -1;
memset(d,-1,sizeof(d) ); //-1代表还未计算过
for( int i = 1; i<=n; i++ )
{
for( int j = 1; j<=m; j++ )
{
res = max( res, dp(i,j) );
}
}
cout << res << endl;
return 0;
}