好贷网好贷款

poj——1088(dp之递归加记忆化搜索)

发布时间:2016-12-3 10:31:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj——1088(dp之递归加记忆化搜索)",主要涉及到poj——1088(dp之递归加记忆化搜索)方面的内容,对于poj——1088(dp之递归加记忆化搜索)感兴趣的同学可以参考一下。

题目地址:http://poj.org/problem?id=1088 小结:可以用递归+记忆化搜索 dp[i][j]:从i j 开始的最长的路径。 dp[i][j] = max {dp[i][j-1], dp[i][j+1], dp[i-1][j], dp[i+1][j], 0} + 1;即当前的路径只与它的上、下、左、右的路径有关。 #include <iostream> #include <cmath> #include <string> #include <cstring> #include <cstdlib> #include <ctime> #include <algorithm> #include <cstdio> #include <map> #include <vector> #include <set> #include <queue> #include <stack> using namespace std; typedef long long ll; #define INF 0x7fffffff #define MAX(a,b) a>b?a:b #define MIN(a,b) a>b?b:a #define N 101 int m,n; int dp[N][N]; int a[N][N]; void init(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) { scanf("%d",&a[i][j]); dp[i][j]=0; } } int dfs(int x,int y){ if(dp[x][y]) return dp[x][y]; int bottom=0,left=0,top=0,right=0; if(x&&a[x-1][y]<a[x][y]) top=dfs(x-1,y); if(y&&a[x][y-1]<a[x][y]) right=dfs(x,y-1); if(x<n-1&&a[x+1][y]<a[x][y]) bottom=dfs(x+1,y); if(y<m-1&&a[x][y+1]<a[x][y]) left=dfs(x,y+1); int maxx=0; maxx=MAX(maxx,left); maxx=MAX(maxx,right); maxx=MAX(maxx,bottom); maxx=MAX(maxx,top); return maxx+1; } void solve(){ int ans=1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { dp[i][j]=dfs(i,j); ans=MAX(ans,dp[i][j]); } printf("%d\n",ans); } int main() { scanf("%d%d",&n,&m); init(); solve(); return 0; }

上一篇:那年,一步一步学linux c ---内存映像~~那些事~~
下一篇:黑马程序员-Java语言基础加强-动态代理模式

相关文章

相关评论