首页 > 代码库 > 百练 1088 滑雪
百练 1088 滑雪
“人人为我”的解法:
dp[i][j]表示坐标为(i,j)的点开始下滑的最大长度。
则dp[i][j]为(i,j)周围四个点中比(i,j)低,且最大长度最大再加一的值
用结构体来储存一个点的坐标和高度,这样按高度从小到大排完序以后还不会丢失坐标的值
从小到大遍历所有的点,经过一个点(i,j)时,用递推公式求L(i,j)。
一个小技巧:
将矩阵height四周的值赋值为INF,你可以想想这是滑雪场四周非常非常高的围墙。
这样就避免了数组越界的判断,而且不会影响正确结果(因为我们找的是滑雪场内部的最大下滑长度)。
最后输出结果的时候,本来是直接输出最高点对应的长度,然后WA了
后来用循环找出最大值再输出就AC了
分析原因可能是这样的,可能有多个最高点,但并不是所有的最高点的下滑长度都是最大的
比如
1 2
2 2
这种情况下最大长度是2,可右下角的最高点对应的下滑长度却是1
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 struct POS 9 {10 int h;11 int x, y;12 }pos[10000 + 10];13 14 bool cmp(POS a, POS b)15 {16 return (a.h < b.h);17 }18 19 const int INF = 100000;20 int height[110][110];21 int dp[110][110];22 23 int main(void)24 {25 #ifdef LOCAL26 freopen("1088in.txt", "r", stdin);27 #endif28 29 int r, c;30 int i, j;31 scanf("%d%d", &r, &c);32 int tot = r * c;33 int cnt = 0;34 for(i = 1; i <= r; ++i)35 for(j = 1; j <= c; ++j)36 {37 scanf("%d", &height[i][j]);38 pos[++cnt].h = height[i][j];39 pos[cnt].x = j;40 pos[cnt].y = i;41 dp[i][j] = 1;42 }43 for(i = 0; i <= c; ++i)44 {45 height[0][i] = height[r+1][i] = INF;46 dp[0][i] = dp[r+1][i] = 1;47 }48 for(i = 0; i <= r; ++i)49 {50 height[i][0] = height[i][c+1] = INF;51 dp[i][0] = dp[i][c+1] = 1;52 }53 sort(pos+1, pos+tot+1, cmp);54 for(i = 2; i <= tot; ++i)55 {56 int x = pos[i].x;57 int y = pos[i].y;58 if(height[y-1][x]<pos[i].h)59 dp[y][x] = max(dp[y][x], dp[y-1][x]+1);60 if(height[y+1][x]<pos[i].h)61 dp[y][x] = max(dp[y][x], dp[y+1][x]+1);62 if(height[y][x-1]<pos[i].h)63 dp[y][x] = max(dp[y][x], dp[y][x-1]+1);64 if(height[y][x+1]<pos[i].h)65 dp[y][x] = max(dp[y][x], dp[y][x+1]+1);66 }67 68 int ans = 1;69 for(i = 1; i <= r; ++i)70 for(j = 1; j <= c; ++j)71 ans = max(ans, dp[i][j]);72 printf("%d\n", ans);73 return 0;74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。