题解 | #滑雪#
滑雪
https://ac.nowcoder.com/acm/problem/235954
这道题利用记忆化搜索，存储每一个点的最优解
类似于dfs，判断从某个点开始能走到的最远位置
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int h[N][N],f[N][N]; //h是高度，f是动态规划里面存从这个点开始能走过的最大距离
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dp(int i,int j)
{
if(f[i][j])return f[i][j]; //如果f[i][j]不为0，那就说明这是从i，j开始的最优解
f[i][j]=1;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(h[x][y]<h[i][j]&&x&&y&&x<=n&&y<=m) //判断高度和是否越界
f[i][j]=max(f[i][j],dp(x,y)+1);
}
return f[i][j];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&h[i][j]);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
ans=max(ans,dp(i,j));
}
cout<<ans<<endl;
return 0;
}
