题目链接
此题运用功能强大的 ~~暴力搜索~~
记忆化搜索才是重点！！！
然而，这是一道经典的DP问题
如果我们用$dis[i][j]$来表示坐标为$(i,j)$时的高度
$cnt[i][j]$ 是我们的记忆化数组
在合法的前提下，就有状态转移方程：
$dis[i][j]=max(dis[i-1][j],dis[i][j-1],dis[i+1][j],dis[i][j+1])$
好啦，直接上代码吧：其实挺暴力:
$2^{33……}$
#include<iostream> #include<cstdio> #include<algorithm> using namespace std;//头文件不说啥 int dis[100][100]; int cnt[100][100]; int row,col;//行列数 inline int DP(int i, int j)//状态转移 { int max1=0; if(cnt[i][j]>0) return cnt[i][j];//记忆化，如果被搜过，跳就好 //判断dis[i][j-1]是否合法 if(j-1>=0)//边界条件 if(dis[i][j]>dis[i][j-1])//转移条件 if(max1<DP(i,j-1)) max1=DP(i,j-1); //判断dis[i][j+1]是否合法 if(j+1<=col-1) if(dis[i][j]>dis[i][j+1]) if(max1<DP(i,j+1)) max1=DP(i,j+1); //判断dis[i-1][j]是否合法 if(i-1>=0) if(dis[i][j]>dis[i-1][j]) if(max1<DP(i-1,j)) max1=DP(i-1,j); //判断dis[i+1][j]是否合法 if(i+1<=row-1) if(dis[i][j]>dis[i+1][j]) if(max1<DP(i+1,j)) max1=DP(i+1,j); return cnt[i][j]=max1+1;//转移 } int main() { scanf("%d%d",&row,&col);//输入 for(int i=0;i<=row-1;i++) for(int j=0;j<=col-1;j++) scanf("%d",&dis[i][j]); for(int i=0;i<=row-1;i++)//状态转移 for(int j=0;j<=col-1;j++) DP(i, j); for(int i=0;i<=row-1;i++)//找最大值 for(int j=0;j<=col-1;j++) if(cnt[0][0]<cnt[i][j]) cnt[0][0]=cnt[i][j]; printf("%d",cnt[0][0]);//输出 return 0;//程序拜拜 }
