摘要
Title: 901. 滑雪
Tag: 记忆化搜索、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

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)