本文主要是介绍POJ 1088 DP || 记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
按高度从小到大排序一遍 DP即可:
#include "stdio.h"
#include "string.h"
#include "queue"
#include "algorithm"
using namespace std;int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,Min,ans;
int a[101][101],dp[101][101];struct node
{int x,y,h;
}data[10010];bool cmp(const node a,const node b)
{return a.h<b.h;
}
void bfs()
{int sum,i,j,x,y;sum=0;for (i=1;i<=n;i++)for (j=1;j<=m;j++){data[sum].x=i;data[sum].y=j;data[sum].h=a[i][j];sum++;}sort(data,data+sum,cmp);for (i=0;i<sum;i++){for (j=0;j<4;j++){x=data[i].x+dir[j][0];y=data[i].y+dir[j][1];if (x<1 || x>n || y<1 || y>m) continue;if (a[x][y]<=a[data[i].x][data[i].y]) continue;dp[x][y]=max(dp[x][y],dp[data[i].x][data[i].y]+1);}}
}int main()
{int i,j;while (scanf("%d%d",&n,&m)!=EOF){Min=10010;for (i=1;i<=n;i++)for (j=1;j<=m;j++){scanf("%d",&a[i][j]);dp[i][j]=1;}bfs();ans=1;for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (dp[i][j]>ans) ans=dp[i][j];printf("%d\n",ans);}return 0;
}
裸记忆化搜索：
<pre name="code" class="cpp">#include "stdio.h"
#include "string.h"
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m;
int dp[101][101];
int a[101][101];
int M(int a,int b)
{if (a<b) return b;else return a;
}
int bfs(int x,int y)
{int ans,i;if (x<1 || x>n || y<1 || y>m) return -1;if (dp[x][y]!=-1) return dp[x][y];ans=1;for (i=0;i<4;i++){if (x+dir[i][0]<1 || x+dir[i][0]>n || y+dir[i][1]<1 || y+dir[i][1]>m) continue;if (a[x][y]<=a[x+dir[i][0]][y+dir[i][1]]) continue;ans=M(ans,bfs(x+dir[i][0],y+dir[i][1])+1);}dp[x][y]=ans;return ans;
}
int main()
{int Max,i,ans,j;while (scanf("%d%d",&n,&m)!=EOF){Max=0;for (i=1;i<=n;i++)for (j=1;j<=m;j++){scanf("%d",&a[i][j]);if (a[i][j]>Max) Max=a[i][j];}memset(dp,-1,sizeof(dp));ans=1;for (i=1;i<=n;i++)for (j=1;j<=m;j++){ans=M(bfs(i,j),ans);}printf("%d\n",ans);}return 0;
}
这篇关于POJ 1088 DP || 记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
