18.滑雪 记忆化搜索

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 310;
 4 int h[N][N]; //h表示每个点的高度 
 5 int f[N][N]; //动态规划数组 
 6 int n, m;
 7 int dx[4] = {-1, 0, 1, 0};
 8 int dy[4] = {0, 1, 0, -1}; //四个方向
 9 int dp(int x, int y) { //dp(i, j)是求出这个状态然后返回
10     int &v = f[x][y]; //引用 
11     if (v != -1) { //表示已经被算过了 
12         return v;
13     }
14     v = 1; //最差最差可以走当前这一个点 
15     for (int i = 0; i < 4; i++) {
16         int a = x + dx[i];
17         int b = y + dy[i];
18         if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) {
19             v = max(v, dp(a, b) + 1);
20         }
21     }
22     return v;
23 }
24 int main() {
25     cin >> n >> m;
26     for (int i = 1; i <= n; i++) {
27         for (int j = 1; j <= m; j++) {
28             cin >> h[i][j];
29         }
30     }
31     memset(f, -1, sizeof f); //表示每个状态都没有被算过 
32     int res = -1; //最大值 
33     for (int i = 1; i <= n; i++) {
34         for (int j = 1; j <= m; j++) {
35             res = max(res, dp(i, j));
36         }
37     }
38     cout << res << endl;
39     return 0;
40 }