首页 > 代码库 > 1434 滑雪
1434 滑雪
难度：普及/提高-
题目类型：记忆化搜索
提交次数：1
涉及知识：动态规划
题目描述
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开始，在1结束）。当然25－24－23―┅―3―2―1更长。事实上，这是最长的一条。
输入输出格式
输入格式：
输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。
输出格式：
输出区域中最长滑坡的长度。
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 using namespace std; 5 int m, n; 6 const int MAXX = 110; 7 const int MAXY = 110; 8 int d[MAXX][MAXY]; 9 bool boundary(int x, int y){10 if(x>=1&&x<=m&&y>=1&&y<=n) return true;11 return false;12 }//判断是否越界13 struct Node{14 int x;15 int y;16 int h;17 };18 bool com(Node a, Node b){19 return a.h < b.h;20 } 21 int main(){22 int i, j, k, x, y;//m行n列 23 cin>>m>>n;24 int a[m+1][n+1];25 k = 0;26 vector<Node>s(m*n);27 for(i = 1; i <= m; i++)28 for(j = 1; j <= n; j++){29 cin>>a[i][j];30 s[k].h = a[i][j];31 s[k].x = i;32 s[k].y = j;33 k++; 34 }35 sort(s.begin(), s.end(), com);//按高度从小到大排序 36 37 for(i = 0; i <= MAXX; i++)38 for(j = 0; j <= MAXY; j++)39 d[i][j] = 1;40 41 for(i = 0; i < m*n; i++){42 if(boundary(s[i].x-1, s[i].y) && a[s[i].x-1][s[i].y] < a[s[i].x][s[i].y])43 d[s[i].x][s[i].y] = max(d[s[i].x][s[i].y], d[s[i].x-1][s[i].y] + 1);44 45 if(boundary(s[i].x+1, s[i].y) && a[s[i].x+1][s[i].y] < a[s[i].x][s[i].y])46 d[s[i].x][s[i].y] = max(d[s[i].x][s[i].y], d[s[i].x+1][s[i].y] + 1);47 48 if(boundary(s[i].x, s[i].y-1) && a[s[i].x][s[i].y-1] < a[s[i].x][s[i].y])49 d[s[i].x][s[i].y] = max(d[s[i].x][s[i].y], d[s[i].x][s[i].y-1] + 1);50 51 if(boundary(s[i].x, s[i].y+1) && a[s[i].x][s[i].y+1] < a[s[i].x][s[i].y])52 d[s[i].x][s[i].y] = max(d[s[i].x][s[i].y], d[s[i].x][s[i].y+1] + 1);53 }54 int ans = 0;55 for(i = 1; i <= m; i++){56 for(j = 1; j <= n; j++)57 ans = max(ans, d[i][j]);58 }59 cout<<ans<<endl;60 return 0;61 }
备注：
暑假北大课讲动规时说过的一道题，回家后写了一遍，洛谷上看到就直接过了。这是比较典型“人人为我”动规。先把点的高度从小到大排序，每个点都初始化为1。从最矮的点开始（每个点都可以从它前后左右任何一个比它高的点滑过来），一步步更新，最后取最大值。
1434 滑雪
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。