信奥赛C++提高组csp-s之搜索进阶（记忆化搜索案例实践1）

信奥赛C++提高组csp-s之搜索进阶（记忆化搜索案例实践1）

滑雪

题目描述

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 24-17-16-124−17−16−1（从24 2424开始，在1 11结束）。当然25 2525－24 2424－23 2323－… \ldots…－3 33－2 22－1 11更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数R RR和列数C CC。下面是R RR行，每行有C CC个数，代表高度（两个数字之间用1 11个空格间隔）。

输出格式

输出区域中最长滑坡的长度。

输入输出样例 1

输入 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

输出 1

25

说明/提示

对于100 % 100\%100%的数据，1 ≤ R , C ≤ 100 1\leq R,C\leq 1001≤R,C≤100。

思路分析

题目大意：

在一个 R×C 的整数矩阵中，找一个点从该点出发，向上下左右四个方向滑行，只能滑向高度严格递减的相邻格子。求最长的滑行路径长度。

分析思路：

如果用暴力DFS，每个点都要重新搜索，会导致大量重复计算。例如，从点A出发搜索到点B的路径时，已经计算过点B出发的最长路径长度；当从点C再经过点B时，又需要重新计算点B的路径，这就是重复计算。

记忆化搜索的做法：

1. 定义f[i][j]表示从点(i, j)出发能滑行的最长路径长度
2. 从每个点出发向四个方向DFS，如果邻点高度小于当前点，则递归求邻点的最长路径
3. 取四个方向的最大值 + 1（当前点自身）
4. 每计算完一个点，就把结果存入f[i][j]，下次再访问该点直接返回

时间复杂度：

每个点只被访问一次，O(R×C)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=105;// 最大矩阵尺寸intn,m;// n行 m列inth[N][N];// h[i][j]存储每个点的高度intf[N][N];// f[i][j]存储从(i,j)出发的最长路径长度，-1表示未计算intdx[4]={-1,1,0,0};// 上下左右四个方向的行偏移intdy[4]={0,0,-1,1};// 上下左右四个方向的列偏移intdfs(intx,inty){// 如果当前点已经计算过，直接返回if(f[x][y]!=-1)returnf[x][y];intans=1;// 当前点至少长度为1（自身）for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];// 边界检查 && 只能往低处滑（严格递减）if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&h[nx][ny]<h[x][y]){ans=max(ans,dfs(nx,ny)+1);}}// 存储结果并返回returnf[x][y]=ans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>h[i][j];}}// 初始化备忘录，-1表示未访问过memset(f,-1,sizeof(f));intres=0;// 枚举每个点作为起点，取最大值for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){res=max(res,dfs(i,j));}}cout<<res<<endl;return0;}

功能分析

正确性保证：由于只能向更低处滑，不会形成环路，DFS终将终止，且每个状态只计算一次，不会超时。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}