记忆化搜索 [SHOI2002]滑雪

[SHOI2002]滑雪
比较经典的记忆化搜索，以前学习过dp，然后就一直没有学记忆化搜索，今天意识到记忆化搜索还是有必要的，因为有时候是从暴力搜索，但是会超时这个角度去考虑问题，搜索的优化自然联想到记忆化处理，确实是个巧妙的手段

#include 
using namespace std;
inline int read() {int f=1,x=0;char c=getchar();while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}
const int MAX=105;
int g[MAX][MAX];
int ans[MAX][MAX];
int n,m,res;
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};inline int dfs(int x,int y) {if (ans[x][y]) return ans[x][y];for (int i=0;i<4;i++) {int nx=x+dx[i];int ny=y+dy[i];if (nx>0&&nx<=n&&ny>0&&ny<=m&&g[nx][ny]<g[x][y]) ans[x][y]=max(ans[x][y],1+dfs(nx,ny));	}	return ans[x][y]=max(1,ans[x][y]);
}int main() {n=read(),m=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)g[i][j]=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) res=max(res,dfs(i,j));printf("%d",res);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！