首页 > 试题广场 >

滑雪

[编程题]滑雪

给定一个 $n \times m \$ 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。

(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)

数据范围： $1 \le n,m \le 100 \$ ，矩阵中的数字满足 $1 \le val \le 1000 \$

第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。

输出最长递减路线。

示例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

从25出发，每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划记忆化搜索图拓扑排序递归

难度：

0条回答 46收藏 2853浏览

查看代码

扫一扫，把题目装进口袋