901. 滑雪_c++一个人滑雪，他的移动可以用一串字符来表示

Powered by:NEFU AB-IN

Link

901. 滑雪

• 题意

  

• 思路

  

  其实就是$dfs$+记忆化，每次爆搜的时候，能利用之前的状态

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-14 09:29:17
  FilePath: \ACM\Acwing\901.py
  LastEditTime: 2022-03-14 17:06:34
  '''
  N = 320
  f = [[-1] * N for _ in range(N)] #先把每个状态初始化为-1，表示状态未被算过
  g = [[0] * N for _ in range(N)]
  
  
  def dp(x, y):
      if f[x][y] != -1:
          return f[x][y]
  
      f[x][y] = 1 # 最少就只走当前的格子
  
      for i in range(4):
          a = x + dx[i]
          b = y + dy[i]
          if a >= 1 and a <= r and b >= 1 and b <= c and g[x][y] > g[a][b]:
              f[x][y] = max(f[x][y], dp(a, b) + 1)
      return f[x][y]
  
  
  r, c = map(int, input().split())
  
  for i in range(1, r + 1):
      g[i][1:] = list(map(int, input().split()))
  
  dx = [-1, 0, 1, 0]
  dy = [0, 1, 0, -1]
  res = 1
  
  for i in range(1, r + 1):
      for j in range(1, c + 1):
          res = max(res, dp(i, j))
  
  print(res)
  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
  34
  35
  36
  37
  38
  39