题目是中文的，要读懂题目其实不难
其实这道题挺经典的，我们这样想，他最终要找到一个最大值，这个时候我们就想到要用动态规划
那怎么用呢？我们同时这样想，由于滑雪的最高点我们不能立马找出来，而且也不一定是最高点就是最长路径的起点。所以我们要不断搜索，我们知道对图的搜索有BFS和DFS，从题目上看，我们应该需要从头走到尾直到找不到路为止，所以我们这题要用DFS，同时，结合我们要用动态规划的思想，我们应该再弄一个矩阵，来保存前面搜索过的路经长，一个点的邻接点如果还没有被搜索过，我们就进入搜索，否则，我们应该直接引用前面已经保存过的路经长，并把搜索过的节点进行标记。
而这样的方法，就是经典的记忆化搜索方法
1 #include2 #include 3 #include 4 #define MAX(a,b) (a)>(b)?(a):(b) 5 6 typedef struct map 7 { 8 int Known; 9 int dist;10 }Dist_Map;11 12 Dist_Map dp[100][100];13 int Input_Map[100][100];14 15 int Search(const int, const int, int *const, int, int);16 17 int main(void)18 {19 int R, C, i, j, Max_Length;20 while (~scanf("%d%d",&R,&C))21 {22 Max_Length = 0;23 24 memset(dp, 0, sizeof(dp));25 for (i = 0; i < R; i++)//读图26 for (j = 0; j < C; j++)27 scanf("%d", &Input_Map[i][j]);28 29 for (i = 0; i < R; i++)30 for (j = 0; j < C; j++)31 if (!dp[i][j].Known)32 Search(R, C, &Max_Length, i, j);33 printf("%d\n", Max_Length);34 }35 return 0;36 }37 38 int Search(const int R, const int C, int *const Max_Length, int py, int px)39 {40 int re_ans;41 dp[py][px].Known = 1; dp[py][px].dist = 1;42 43 if (py - 1 >= 0 && Input_Map[py][px] > Input_Map[py - 1][px])44 {45 if (!dp[py - 1][px].Known)46 re_ans = Search(R, C, Max_Length, py - 1, px);47 else48 re_ans = dp[py - 1][px].dist;49 dp[py][px].dist = MAX(re_ans + 1, dp[py][px].dist);50 51 }52 if (py + 1 < R && Input_Map[py][px] > Input_Map[py + 1][px])53 {54 if (!dp[py + 1][px].Known)55 re_ans = Search(R, C, Max_Length, py + 1, px);56 else57 re_ans = dp[py + 1][px].dist;58 dp[py][px].dist = MAX(re_ans + 1, dp[py][px].dist);59 }60 if (px - 1 >= 0&& Input_Map[py][px] > Input_Map[py][px - 1])61 {62 if (!dp[py][px - 1].Known)63 re_ans = Search(R, C, Max_Length, py, px - 1);64 else65 re_ans = dp[py][px - 1].dist;66 dp[py][px].dist = MAX(re_ans + 1, dp[py][px].dist);67 }68 if (px + 1 < C && Input_Map[py][px] > Input_Map[py][px + 1])69 {70 if (!dp[py][px + 1].Known)71 re_ans = Search(R, C, Max_Length, py, px + 1);72 else73 re_ans = dp[py][px + 1].dist;74 dp[py][px].dist = MAX(re_ans + 1, dp[py][px].dist);75 }76 77 *Max_Length = MAX(dp[py][px].dist, *Max_Length);78 return dp[py][px].dist;79 }