【SHOI2002】【Luogu1434】滑雪（记忆化）

problem

solution

codes

//f[i][j]:以(i,j)为终点的最长路是是多少
//f[i][j] = f(它四周的比他高的方块的最长路)+1
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 110;
int r, c, a[maxn][maxn], f[maxn][maxn], ans;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
bool inside(int x, int y){return x>=1&&x<=r&&y>=1&&y<=c;}
int dp(int x, int y){
    if(f[x][y])return f[x][y];
    int res = 0;
    for(int i = 0; i < 4; i++){
        int nx = x+dx[i], ny = y+dy[i];
        if(inside(nx,ny)&&a[nx][ny]>a[x][y]){
            res = max(res,dp(nx,ny));
        }
    }
    return f[x][y]=res+1;//我竟然因为没有更新f[x][y]导致第二个点没过。。
}
int main(){
    ios::sync_with_stdio(false);
    cin>>r>>c;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            cin>>a[i][j];
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            ans = max(ans,dp(i,j));
    cout<<ans;
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80465546