1.6　滑雪

【题目描述】 滑雪（ski）

小光喜欢滑雪，因为这项运动很刺激。为了获得更快的速度，滑的区域必须向下倾斜。因此，小光滑到坡底后，不得不再次走路或坐缆车到坡顶。小光想知道在一个区域中最长滑坡的长度。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，二维数组的每个数字代表点的高度。

例如有样例：

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

一个人可以从某个点滑向上下左右相邻的4个点中的一个点。当且仅当高度减小时，在上面的例子中，一条可行的滑坡为25→24→17→16→1。当然，25→24→23→…→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

【算法分析】

对于任意一个点[i][j]，当它的高度小于与之相邻的4个点的高度时，可以从这4个点滑向 点[i][j]。用f[i][j]表示到点[i][j]的最大长度，则f[i][j]=max{f[i+a][j+b]}+1，其中i+a和j+b代表其周围4个点的坐标。为了在计算出f[i][j]之前计算出f[i+a][j+b]，需要对高度进行排序，然后从大到小规划高度，最后再比较所有的f[i][j]，找出其中最长的一条路线。

但如果用记忆化搜索算法，则不需要进行排序，且能保证每个点的路径只求一次，只需利用递归算法逐点求出区域中此点的最长路径。

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效的状态，特别是搜索可以进行剪枝，因此搜索在空间开销上往往比动态规划要低很多。

如何解决动态规划的高效率与高开销之间的矛盾呢？

有一个折中的办法就是使用记忆化搜索算法。使用记忆化搜索算法在求解的时候还是按照自顶向下的顺序，但是每求解一个状态，就将解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划的优点。

参考代码如下。

 1    //滑雪
 2    #include <bits/stdc++.h>
 3    using namespace std;
 4    const int DX[4]= {-1,0,1,0};                    //横坐标的增量数组
 5    const int DY[4]= {0,1,0,-1};                    //纵坐标的增量数组
 6
 7    int m[101][101],f[101][101];
 8    int r,c;
 9
10    int Search(int x,int y)                         //求到点(x,y)的最长路径
11    {
12      if(f[x][y]>0)                                 //如果此点出发的路径长度已求出
13        return f[x][y];                             //则无须递归
14      f[x][y]=1;                                    //自身初始长度就是1
15      for(int i=0; i<=3; i++)                       //从4个点中搜索能到达点(x,y)的点
16      {
17        int nx=x+DX[i];                             //加上横坐标增量
18        int ny=y+DY[i];                             //加上纵坐标增量
19        if(nx>=1 && nx<=r && ny>=1 && ny<=c && m[x][y]<m[nx][ny])
20          f[x][y]=max(Search(nx,ny)+1,f[x][y]);     //递归进行记忆化搜索
21      }
22      return f[x][y];
23    }
24
25    int main()
26    {
27      scanf("%d%d",&r,&c);
28      for(int i=1; i<=r; i++)
29        for(int j=1; j<=c; j++)
30          scanf("%d",&m[i][j]);
31      int ans=0;
32      for(int i=1; i<=r; i++)
33        for(int j=1; j<=c; j++)
34        {
35          f[i][j]=Search(i,j);
36          ans=max(f[i][j],ans);
37        }
38      printf("%d\n",ans);
39      return 0;
40    }