简答题
偏难
#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 <cmath>
#include <cstdio>
#include <iostream>
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 < 4; i++) {
int tx = dx[i] + x, ty = dy[i] + y;
if (tx > 0 && tx <= n && ty >= 1 && ty <= m && a[x][y] > 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", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs
printf("%d", ans);
return 0;
}</pre>
解析
解题思路
采用递推的动态规划方式求解
先用结构体保存每个点对应的原本坐标位置和高度;
将所有点按高度从小到大排序;
用一个二维数组保存输入的原本数据,
再用一个二维数组保存对应位置的最大滑行距离;
从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)
依次和它在原本坐标里的上下左右四个方向进行判断,
如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。
最后求完总共的点,进行遍历,得到最终最大值。