给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300 0≤矩阵中整数≤10000
输入样例：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例：
25
思路：关键在于记忆化搜索，就是Z采用递归的思想，f[i,j]暂时求不出来，用递归函数dp[i,j]表示，当满足条件向右滑行时，f[i,j]=f[i,j+1]+1; 要选择前后左后四个方向的最大值即是题意 所以取f[i,j]的最大值就是如下图中max（f(i,j+1),f(i-1,j),f(i,j-1),f(i+1,j)) 又因为f(i,j)往下递推的值都不知道，所以用dp数组来保存，这是和一般动态规划问题的区别
完整代码：
#include
#include
using namespace std;
int n,m;
const int N=310;
int f[N][N],h[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dp(int x,int y){
int &v=f[x][y];
if(v!=-1)return v;
v=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b] } return v; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>h[i][j]; int res=0; memset(f,-1,sizeof f); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) res=max(res,dp(i,j)); cout< } 相关阅读
发表评论