信奥赛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 252524 242423 2323… \ldots…3 332 221 11更长。事实上这是最长的一条。输入格式输入的第一行为表示区域的二维数组的行数R RR和列数C CC。下面是R RR行每行有C CC个数代表高度两个数字之间用1 11个空格间隔。输出格式输出区域中最长滑坡的长度。输入输出样例 1输入 15 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输出 125说明/提示对于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的路径这就是重复计算。记忆化搜索的做法定义f[i][j]表示从点(i, j)出发能滑行的最长路径长度从每个点出发向四个方向DFS如果邻点高度小于当前点则递归求邻点的最长路径取四个方向的最大值 1当前点自身每计算完一个点就把结果存入f[i][j]下次再访问该点直接返回时间复杂度每个点只被访问一次O(R×C)。代码实现#includebits/stdc.husingnamespacestd;constintN105;// 最大矩阵尺寸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];intans1;// 当前点至少长度为1自身for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 边界检查 只能往低处滑严格递减if(nx1nxnny1nymh[nx][ny]h[x][y]){ansmax(ans,dfs(nx,ny)1);}}// 存储结果并返回returnf[x][y]ans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;in;i){for(intj1;jm;j){cinh[i][j];}}// 初始化备忘录-1表示未访问过memset(f,-1,sizeof(f));intres0;// 枚举每个点作为起点取最大值for(inti1;in;i){for(intj1;jm;j){resmax(res,dfs(i,j));}}coutresendl;return0;}功能分析模块功能说明备忘录数组f[N][N]存储每个点出发的最长路径长度-1表示未计算避免重复DFS方向数组dx[], dy[]简化四个方向的遍历代码dfs(x, y)核心递归函数返回从(x,y)出发的最长滑行长度边界检查确保不会走出矩阵范围高度递减判断只能向高度更低的格子滑保证不形成循环枚举所有起点因为不知道最长路径从哪个点开始所以每个点都要尝试正确性保证由于只能向更低处滑不会形成环路DFS终将终止且每个状态只计算一次不会超时。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}