滑雪(DP,记忆化搜索)

原题：

滑雪

时间限制: 1 Sec  内存限制: 256 MB

题目描述

　　Michael喜欢滑雪。这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子。

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-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

输入

　　第一行表示有几组测试数据，输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。　　后面是下一组数据；

输出

　　输出最长区域的长度。

样例输入

1

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

---

题意：

　　在R*C的矩阵中寻一条路径，并使其严格下降，求最长的路径长度。

　　这道题正解是DP思想中的记忆化搜索，用s数组记录从s[i][j]出发可以到达的最远距离。

　　怎么思考呢？我们先用暴力dfs来依次枚举每一个点找最长路径（代码不贴了），虽然可以找到最短路径，但很明显会超时。

　　分析一下思路：每次枚举到一个点的时候，我们都会向它的四个方向拓展，如果高度比当前点低就再次拓展，有时候一个点已经在之前的dfs中枚举过了，再次拓展到这个点的时候需要再尝试一遍，岂不是很浪费？

　　所以我们试着储存之前尝试过的结果，下次到达一个已经搜索过的点就可以直接调用，节省了很多时间，这也是记忆化搜索的原因和优化方法。

---

　　控制方向的简单小技巧：

　　对于当前点(x,y)而言，它的上、下、左、右坐标分别为(x-1,y)，(x+1,y)，(x,y-1)，(x,y+1)，转换方向时相当于直接在原来的坐标上操作，因此我们可以开两个数组dx，dy配套使用，转换方向就在原坐标基础上分别加上dx[i]，dy[i]，如（不完整代码，(tx,ty)为转方向后的坐标）：

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
...
int tx=x+dx[i],ty=y+dy[i];

---

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
//控制方向的常用方法 
int n,m,a[205][205],s[205][205],ans;
int dfs(int x,int y)
{
    if(s[x][y])  return s[x][y];
    s[x][y]=1;//自身算一个距离 
    for(int i=0;i<4;i++)
    {
        int tx=dx[i]+x,ty=dy[i]+y;
           if(tx>0 && tx<=n && ty>=1 && ty<=m && a[x][y]>a[tx][ty])
        {
            dfs(tx,ty);
            s[x][y]=max(s[x][y],s[tx][ty]+1);
            //记忆化 
        }
    }
return s[x][y];
}
int main()
{    
    scanf("%d%d",&n,&m);
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
               scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,dfs(i,j));//将每个点当成起点做dfs 
    printf("%d",ans);
return 0;
}