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;}