简答题 偏难
#7254

滑雪 Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你…

滑雪

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。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

时间限制:1000

内存限制:65536

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。

输出

输出最长区域的长度。

样例输入

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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;iostream&gt; using namespace std; int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; // 控制方向的常用方法 int n, m, a[205][205], s[205][205], ans; int dfs(int x, int y) {   if (s[x][y])     return s[x][y];   s[x][y] = 1; // 自身算一个距离   for (int i = 0; i &lt; 4; i++) {     int tx = dx[i] + x, ty = dy[i] + y;     if (tx &gt; 0 &amp;&amp; tx &lt;= n &amp;&amp; ty &gt;= 1 &amp;&amp; ty &lt;= m &amp;&amp; a[x][y] &gt; a[tx][ty]) {       dfs(tx, ty);       s[x][y] = max(s[x][y], s[tx][ty] + 1);       // 记忆化     }   }   return s[x][y]; } int main() {   scanf("%d%d", &amp;n, &amp;m);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= m; j++)       scanf("%d", &amp;a[i][j]);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= m; j++)       ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs   printf("%d", ans);   return 0; }</pre>
解析

解题思路

采用递推的动态规划方式求解

先用结构体保存每个点对应的原本坐标位置和高度;

将所有点按高度从小到大排序;

用一个二维数组保存输入的原本数据,

再用一个二维数组保存对应位置的最大滑行距离;

从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)

依次和它在原本坐标里的上下左右四个方向进行判断,

如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。

最后求完总共的点,进行遍历,得到最终最大值。