Python教程

AcWing901. 滑雪(python)

本文主要是介绍AcWing901. 滑雪(python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目详情


知识点

记忆化DP

思路

自己的思路(仅参考):一开始想的是找最大值,然后从最大值开始向下滑,但是我们是要求最长路径,不一定是从最高的点滑下去的,也不一定是滑到最低点,而且会存在最大值不止一个的情况,所以我们应该是针对每一个点,都求出当前该点出发能去的最长路径,然后求完之后再遍历一边找到最大值就可以了

f[i,j]=max(四个方向的dp+1)

要注意有时候这四个方向并不是都可以走的,我们在枚举的时候要处理不能走的情况(比如越界、比如坡度不合适)

dp能做的前提:状态转换是一个拓扑图,也就是我们的状态转换关系中不能存在环,而是有一个顺序可以逐渐全部求解出来的

这道题的关键就是讲一种实现方式:全新的实现方式——递归

我们要初始化f为-1,表示从来没有访问过这个点,在之后再次调用到f的时候,如果它的值不为-1,就直接返回f的值,不用再算一遍了

python选手需要注意的一个点:python3默认的栈的深度比较小,用递归的时候可能会爆栈,所以要加上这样两行代码防止爆栈

import sys
sys.setrecursionlimit(100000) # 防止爆栈

代码

import sys
sys.setrecursionlimit(100000) # 防止爆栈
n,m = map(int,input().split())
h = [[]for i in range (n+1)]
for i in range(1,n+1):
    h[i] = list(map(int,("0 "+input()).split()))
f = [[-1 for i in range(m+1)]for i in range(n+1)] # -1表示这个状态没被算过

dx = [0,1,0,-1]
dy = [1,0,-1,0]

def dp(x,y):
    if f[x][y] != -1: return f[x][y]
    f[x][y] = 1 # 这个初始化别忘了
    for i in range(4):
        a,b = x+dx[i],y+dy[i]
        if 1 <= a <= n and 1 <= b <= m and h[a][b] < h[x][y]:
            f[x][y] = max(f[x][y],dp(a,b)+1)
    return f[x][y]

res = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        # 枚举从每个点出发
        res = max(res,dp(i,j))
        # dp(i,j)
print(res)
这篇关于AcWing901. 滑雪(python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!