AcWing 901. 滑雪
原题链接
简单
作者:
B1ackGod
,
2021-02-10 01:04:19
,
所有人可见
,
阅读 412
核心;动态规划,利用记忆化搜索,保留之前递归求的值,需要用的时候直接返回就可以了
- 状态定义:f[i][j]表示以(i,j)为起点的所有路径
- 属性:max,最长的路径
- 状态计算:以上下左右四个方向划分集合
例如:向右滑雪,(i,j)–>(i,j+1)–>…可以等价于从(i,j)到(i,j+1)+以(i,j+1)为起点的路径
那么f[i][j]=f[i,j+1]+1,当然,转移的条件就是高度(i,j)>(i,j+1)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int f[N][N];
int g[N][N];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int n,m;
int dfs(int x, int y){
if(f[x][y]!=0) return f[x][y];//如果搜索过,就直接返回不需要进行重复搜索
f[x][y]=1;//如果四个方向都无法移动,只能走当前这个格子
for(int i=0;i<4;i++)
{
int x1=x+dx[i],y1=y+dy[i];
//判断坐标是否合法
if(x1>=1 && y1>=1 && x1<=n && y1<=m && g[x][y]>g[x1][y1] ){
f[x][y]=max(f[x][y],dfs(x1,y1)+1);
}
}
return f[x][y];
}
int main(){
cin>>n>>m;
int maxlen=-1e5;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin>>g[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
maxlen=max(maxlen,dfs(i,j));
}
printf("%d",maxlen);
return 0;
}