首页 > 代码库 > 百练 1088 滑雪

百练 1088 滑雪

2024-07-12 18:36:48   227人阅读

“人人为我”的解法：

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 }
代码君


联系
我们