滑雪c++【记忆化搜索】

题目描述：

滑雪
题目描述

很多人喜欢滑雪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。现在想知道在一个区域中最长底滑坡。

区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

 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

改变方向直接xx = x + dx[i] , yy = y + dy[i]
判断是否在地图内直接xx >= 1 && xx <= n && yy >= 1 && yy <= m
判断是否能滑得到直接g[xx][yy] < g[x][y]

这道题不能写普通的爆s，要记忆化：
f[i][j]表示从(i,j)点出发能走的最长距离，每次s的时候记忆一次就可以了，记忆化搜索CODE：

#include 

using namespace std ;

const int N = 1010 ;
int n , m , res ;
int g[N][N] , f[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 ;
    else v = 1 ;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i] , yy = y + dy[i] ;
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[x][y] > g[xx][yy])
        {
            v = max (v , dp (xx , yy) + 1) ;
        }
    }
    return v ;
}

int main ()
{


    cin >> n >> m ;
    memset (f , -1 , sizeof (f)) ;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)  cin >> g[i][j] ;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) res = max (res , dp (i , j)) ;
    }
    cout << res << endl ;


	return 0 ;
}