P1434 滑雪【洛谷算法习题】-北京尧图网络

P1434 滑雪网页链接P1434 滑雪题目描述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 − 24 − 23 − … − 3 − 2 − 1 25-24-23-\ldots-3-2-125−24−23−…−3−2−1更长。事实上这是最长的一条。输入格式输入的第一行为表示区域的二维数组的行数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。对于任意输入的高度h hh满足0 ≤ h ≤ 10000 0 \le h \le 100000≤h≤10000且h hh是整数。解题思路本题是**记忆化搜索记忆化DFS**的经典入门题利用高度严格递减的无环性质通过缓存每个点的最长路径结果避免重复计算在线性时间内求解二维网格的最长下降路径。状态定义定义s[x][y]表示以格子(x, y)为起点的最长滑坡长度。由于只能向高度更低的方向滑动路径天然无环每个点的结果只依赖于相邻更低点的结果满足动态规划的最优子结构性质。状态转移对于每个格子(x, y)枚举上下左右四个相邻方向若相邻格子在边界内且高度严格小于当前格子则可以从当前格子滑向该相邻格子。当前格子的最长路径所有合法相邻格子的最长路径 1取所有方向中的最大值。初始值每个格子自身构成一条长度为1的路径即s[x][y] 1。记忆化实现采用深度优先搜索计算每个点的结果同时用s数组缓存已计算的结果若s[x][y]不为0说明该点已计算过直接返回缓存值避免重复递归。若未计算则初始化长度为1遍历四个方向递归求解并更新最大值最后将结果存入缓存再返回。结果统计遍历网格中所有格子以每个点为起点计算最长滑坡长度取全局最大值即为最终答案。算法总时间复杂度为O ( R × C ) O(R \times C)O(R×C)每个格子仅被计算一次每次计算遍历4个方向完全适配100×100的数据规模。总结核心逻辑基于高度严格递减的无环特性通过记忆化DFS缓存每个起点的最长路径长度避免重复计算高效求得全局最长滑坡。关键操作记忆化数组缓存结果、四方向遍历边界校验、递归求解子问题、全局最大值统计。效率保障每个点仅计算一次线性时间复杂度百级网格无任何性能压力。代码简要说明方向数组dx、dy数组定义上下左右四个方向的坐标偏移量用于批量遍历相邻格子。记忆化DFS函数若s[x][y]非零直接返回缓存值避免重复计算。初始化当前路径长度为1遍历四个方向校验边界与高度递减条件。递归计算相邻格子的最长路径更新当前格子的最大值存入缓存后返回。主函数逻辑读入行数n、列数m以及二维高度数组a。双重循环遍历所有格子调用DFS计算每个起点的最长路径同步更新全局最大值ans。输出最终的最长滑坡长度。输入输出使用scanf/printf保证读写效率适配常规数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m;ll dx[4]{0,0,1,-1};ll dy[4]{1,-1,0,0};ll a[205][205],s[205][205],ans;lldfs(ll x,ll y){if(s[x][y])returns[x][y];s[x][y]1;for(ll i0;i4;i){ll xxxdx[i],yyydy[i];if(xx0yy0xxnyyma[x][y]a[xx][yy]){dfs(xx,yy);s[x][y]max(s[x][y],s[xx][yy]1);}}returns[x][y];}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);for(ll i1;in;i)for(ll j1;jm;j)scanf(%lld,a[i][j]);for(ll i1;in;i)for(ll j1;jm;j)ansmax(ans,dfs(i,j));printf(%lld,ans);return0;}

P1434 滑雪【洛谷算法习题】

相关推荐

【办公类-54-11】20260901营养员《每周人数统计表》（双休日和国定假日填充灰色或填充白色、EXCEL+PDF，三个园区两种代码和两个excel，有XX节放假）

3分钟彻底清理Windows右键菜单：ContextMenuManager完全使用指南

TPA3128D2与ARM Cortex-M4构建高效音频放大系统

更多资讯

DDPG在航空冲突解脱中的工程实践与OpenScope仿真落地

从550GB到1MB：HJB方程的牛顿策略迭代与Tensor Train压缩

深度学习+蚁群算法：羽毛球战术决策的组合优化实践

金融风控欺诈检测全流程：从数据预处理到模型部署的避坑指南

Java openNLP模型训练、保存加载与推断工程避坑

A股量化分析工具OpenClaw：8大核心功能解析与应用

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？