滑雪
思路:题意要求出滑行线路的最大值,滑行线路必须是递减的线路。根据动态规划思想要求出从i行j列上滑下的最大距离线路等于i行j列这个点四周点的最大距离+1。
实现:定义mp,sum数组分别存放原始二维数组,存放与之对应的最大长度数组。a结构体数组记录的是每个点在原始数组对应的坐标位置和高度值。用sort对a结构体数组升序排序能够保证高度高的点能够寻找出四周高度低的点的最大距离。最后对sum数组进行遍历找出最大距离的点。
代码
#include<iostream>
#include<algorithm>
using namespace std;
int mp[101][101], sum[101][101];//全局变量自动初始化为0,mp存放初始数值,sum存放i行j列上元素的最长区域长度
int dr[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
struct a {
int value;
int x, y;
}a[10001];
bool cmp(struct a x, struct a y) {
return x.value < y.value;
}
int main() {
int t, i, j, n, m, count = 0;//n行m列,一共count个数
cin >> n >> m;
for(i=1;i<=n;i++)
for (j = 1; j <= m; j++) {
cin >> t;
a[count].x = i;
a[count].y = j;
a[count++].value = mp[i][j] = t;
}
sort(a, a + count,cmp);
//类似广搜
for (i = 0; i < count; i++) {
t = 0;//t为寻找四个方向上最长路径的走法
for (j = 0; j < 4; j++) {
int dx = a[i].x + dr[j][0];
int dy = a[i].y + dr[j][1];
if (dx<1 || dy<1 || dx>n || dy>m)//检查a[i]这个点的四个方向上的数字是否越界
continue;
if (a[i].value > mp[dx][dy])//检查该点的值是否满足大于四周的值,否则滑不上去(虽然结构体a升序排序了,但是遇到数值相等的情况下不加上这句就会错误)
t = max(sum[dx][dy], t);
}
t++;//每个点的路径最少为1,故在此t++
sum[a[i].x][a[i].y] = t;
}
t = -1;
for(i=1;i<=n;i++)//寻找最大值
for (j = 1; j <= m; j++) {
t = max(t, sum[i][j]);
}
cout << t;
return 0;
}

京公网安备 11010502036488号