DP 滑雪(记忆化搜索）_1280：【例9.24】滑雪

【例9.24】滑雪

时间限制: 1000 ms        内存限制: 65536 KB
提交数: 312     通过数: 139 

【题目描述】

小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：

1161514132172423123182522114192021105678912345161718196152425207142322218131211109

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为25-24-17-16-1（从25开始到1结束），当然25-24……2-1更长，事实上这是最长的一条。

【输入】

输入的第一行为表示区域的二维数组的行数R和列数C（1≤R、C≤100），下面是R行，每行有C个数代表高度。

【输出】

输出区域中最长的滑坡长度。

【输入样例】

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

【来源】

No

算法分析：

设f[i][j]为到i，j为止的最长长度

记忆化搜索，如果满足周围四个点低于其点（且在范围内）则递归+1

状态转移方程 f[i][j]=max{f[i+a][j+b]}+1;

代码实现：

 

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,1,0,-1,0},//坐标x的增量
    dy[5]={0,0,1,0,-1};//坐标y的增量
long f[105][105],a[105][105];
long i,j,n,m,t;
int search(int x,int y)           //求出到[x,y]的最长路径
{
    if(f[x][y]>0)  return f[x][y];//如果f[x][y]已经算过(每点只求一次），则直接返回其值（记忆化搜索）
     int temp;
     t=1;
     for(int k=1;k<=4;k++)  //四个方向搜搜能到[x,y]的点
     {
         if(x+dx[k]<=n&&x+dx[k]>=1&&y+dy[k]<=m&&y+dy[k]>=1&&a[x+dx[k]][y+dy[k]]>a[x][y])//边界限制，高度比较
         {
            temp=search(x+dx[k],y+dy[k])+1;//成立就加1
            if(temp>t)  t=temp;
         }
     }
     f[x][y]=t;
     return t;
}
int main()
{
 
  cin>>n>>m;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     cin>>a[i][j];
  int ans=0;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
        t=search(i,j);   //逐点求出到此点的最长长度
        f[i][j]=t;
        if(t>ans)
        ans=t;
    }
    cout<<ans<<endl;
  return 0;
}