滑雪

描述：

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
这道题目写出记忆化搜索(递归)形式不难,但递推形式要一点技巧;

#include <bits/stdc++.h> using namespace std; int row, line, counter = 1, dp[100000], dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};//这里dx,dy是写方向的常见写法; struct E {     int x;     int y;     int h; } maper[100000];
bool rule1(E a, E b) {     return a.h < b.h; }
bool ifaround(int i, int j) {     for (int k = 0; k < 4; k++)     {         int rex = maper[i].x + dx[k];         int rey = maper[i].y + dy[k];         if (rex == maper[j].x && rey == maper[j].y)         {             return true;         }     }     return false; }
int main() {     //输入数据;     cin >> row >> line;     //将二维数组转化为一维数组,便于递推;     for (int i = 1; i <= row; i++)     {         for (int j = 1; j <= line; j++)         {             dp[counter] = 1;//这里再强调一下memset只能初始化0,-1而不是1;             maper[counter].x = j;             maper[counter].y = i;             cin >> maper[counter].h;             counter++;         }     }     //将数组按高度从小到大排列;     sort(maper + 1, maper + counter, rule1);     //递推dp数组;     for (int i = 1; i < counter; i++)     {         for (int j = i - 1; j >= 1; j--)         {             if (ifaround(i, j) && maper[i].h > maper[j].h )//这里加上maper[i].h > maper[j].h 是为了防止高度重复的情况;             {                 //因为有4种走法,要选出最大长度的走法;                 dp[i] = max(dp[j] + 1, dp[i]);             }         }     }     int answer = 0;     for (int i = 1; i < counter; i++)     {         answer = max(answer, dp[i]);     }     cout << answer;     return 0; } 多亏了这位大佬的测试数据让我写出来了:https://blog.csdn.net/huanghanqian/article/details/51646241;