滑雪问题（记忆化搜索）

注：由于本题有多种不同版本，这里统一用XXX和YYY代替不同的专有名词

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

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

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

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 500)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

输出最长区域的长度。

input

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

output

25

时间限制：2s
空间限制：128MB

本题的测试数据有着一定的误导性，有些人在开始会直接出现两个错误思路：

1. 从单个或多个最高点开始的路径一定最长
2. 每次选择与当前点落差最小的点作为下一个点的路径一定最长
3. 前两种思路全部出现

这三种情况实际上只要稍稍想一想就能发现反例，就看你能否仔细思考反问了

爆搜思路：将每个点作为起始点，向四个方向中合法的点试最长路径
这样有多层嵌套循环的题目，单纯的爆搜基本上都会爆时间 有空可以算一下
所以需要在DFS时带上记忆化，用全局数组记录每个点自身为起始点时的最长路径，需要时直接取用
更详细请看下面代码与注释↓

#include
using namespace std;
typedef struct node
{
	int h,path;//h：此点的高度，path：以该点为起始点时的最长路径
}NODE,*PNODE;
NODE a[501][501];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0},n,m;
int calc(int x,int y)
{
	if(a[x][y].path)
		return a[x][y].path;//如果已经有了路径，直接返回即可，非常省时
	int i,x1,y1,maxx=0,t;
	for(i=0;i<4;i++)
	{
		x1=x+dx[i];
		y1=y+dy[i];//下一个点
		if(x1>0&&x1<=n&&y1>0&&y1<=m&&a[x1][y1].h
			t=calc(x1,y1);//继续递归计算
			maxx=max(maxx,t);//更新最大路径
		}
	}
	return a[x][y].path=maxx+1;//这里处理的稍微简洁了一点
}
int main()
{
	int i,j,t,ans=0;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j].h);//接收数据
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			t=calc(i,j);
			ans=max(ans,t);
		}
	printf("%d",ans);
	return 0;
}