滑雪摔出阴影的我一脚把题目踹上来----》
【题目描述】
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。
【输出】
输出最长区域的长度。
【输入示例】
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
第一眼我仍然把它看成深搜，但是看了数据范围之后我就和深搜说拜拜。
嗯，我只好拿出我刚学不到两天的记忆化搜索来凑数。
现在我们来把程序拆解一下：
思路：计算每个点到山脚的最长路程。
1 int up=0,down=0,left=0,right=0;
2 if(x-1>0)
3 {
4 if(map[x-1][y]<map[x][y])
5 {
6 up=snow(x-1,y)+1;
7 }
8 }
9 if(x+1<=mx)
10 {
11 if(map[x+1][y]<map[x][y])
12 {
13 down=snow(x+1,y)+1;
14 }
15 }
16 if(y-1>0)
17 {
18 if(map[x][y-1]<map[x][y])
19 {
20 left=snow(x,y-1)+1;
21 }
22 }
23 if(y+1<=my)
24 {
25 if(map[x][y+1]<map[x][y])
26 {
27 right=snow(x,y+1)+1;
28 }
29 }
看这个山坡的上下左右，如果比查找的山坡矮，则寻找这个山坡的最长路程。↑
1 if(up<down)
2 {
3 up=down;
4 }
5 if(up<left)
6 {
7 up=left;
8 }
9 if(up<right)
10 {
11 up=right;
12 }
13 return up
然后比较上下左右的最长路程，看哪个最长，就是这个山坡到山脚的最长路程。↑
1 if(move[x][y]>0)
2 {
3 return move[x][y];
4 }
注意，如果这个山坡的最长路程已经确定，那么直接返回，可以节省时间。↑
完整代码见下方：
1 #include<iostream>
2 using namespace std;
3 int map[113][113];
4 int move[113][113];
5 int mx,my;
6 int snow(int x,int y)
7 {
8 if(move[x][y]>0)
9 {
10 return move[x][y];
11 }
12 int up=0,down=0,left=0,right=0;
13 if(x-1>0)
14 {
15 if(map[x-1][y]<map[x][y])
16 {
17 up=snow(x-1,y)+1;
18 }
19 }
20 if(x+1<=mx)
21 {
22 if(map[x+1][y]<map[x][y])
23 {
24 down=snow(x+1,y)+1;
25 }
26 }
27 if(y-1>0)
28 {
29 if(map[x][y-1]<map[x][y])
30 {
31 left=snow(x,y-1)+1;
32 }
33 }
34 if(y+1<=my)
35 {
36 if(map[x][y+1]<map[x][y])
37 {
38 right=snow(x,y+1)+1;
39 }
40 }
41 if(up<down)
42 {
43 up=down;
44 }
45 if(up<left)
46 {
47 up=left;
48 }
49 if(up<right)
50 {
51 up=right;
52 }
53 return up;
54 }
55 int main()
56 {
57 int max1=0;
58 cin>>mx>>my;
59 for(int i=1;i<=mx;i++)
60 {
61 for(int j=1;j<=my;j++)
62 {
63 cin>>map[i][j];
64 }
65 }
66 for(int i=1;i<=mx;i++)
67 {
68 for(int j=1;j<=my;j++)
69 {
70 move[i][j]=snow(i,j);
71 if(move[i][j]>max1)
72 {
73 max1=move[i][j];
74 }
75 }
76 }
77 cout<<max1+1;
78 }
好吧，一道记忆化搜索~~~。
讲真我滑雪的时候才不会管怎么滑路程最长呢。
在暴风雨中低着头，是为了不让雨水模糊风雨后眼中的彩虹。