1338 滑雪(ski) 题解

红小豆

题目传送门
设平面上的点（x，y）表示这个点最多能再往下滑的方块数
枚举周围的4个点，四个点求得的最大值加一就是这个点最多能再往下滑的方块数（这里是递归调用）
注意下边界，不能出了地图！
时间复杂度O（RC）

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. int mp[105][105],r,c,dp[105][105];
   
5. int fx[6][3] = {
   
6. {1,0},
   
7. {-1,0},
   
8. {0,1},
   
9. {0,-1},
   
10. };
    
11. int dfs(int x,int y){
    
12.         if (dp[x][y] != 0) return dp[x][y];
    
13.         int maxn = 1;
    
14.         for (int i = 0;i < 4;i++){
    
15.                 int xx = x + fx[i][0];
    
16.                 int yy = y + fx[i][1];
    
17.                 if (xx >= 1 && yy >= 1 && xx <= r && yy <= c){
    
18.                         if (mp[xx][yy] < mp[x][y]){
    
19.                                 maxn = max(maxn,dfs(xx,yy) + 1);
    
20.                         }
    
21.                 }
    
22.         }
    
23.         dp[x][y] = maxn;
    
24.         return dp[x][y];
    
25. }
    
26. int main(){
    
27.         cin >> r >> c;
    
28.         for (int i = 1;i <= r;i++){
    
29.                 for (int j = 1;j <= c;j++){
    
30.                         cin >> mp[i][j];
    
31.                 }
    
32.         }
    
33.         int maxn = 0;
    
34.         for (int i = 1;i <= r;i++){
    
35.                 for (int j = 1;j <= c;j++){
    
36.                         maxn = max(maxn,dfs(i,j));
    
37.                 }
    
38.         }
    
39.         cout << maxn;
    
40. return 0;
    
41. }

复制代码