P2196 [NOIP1996 提高组] 挖地雷 详细python题解

蒟蒻dp没有解出来，这道题python的题解也很少很少，所以写了py 的dfs 的解法

灰常详细（doge）

话不多数，直接上代码

n = int(input())
value_arr = list(map(int,input().split(" "))) #所挖宝藏的价值
graph_arr = []

for i in range(n-1):
    graph_arr.append(list(map(int,input().split(" ")))) #建立图
graph_arr.append([0])

def dfs(node,road="", res = 0,): #每一个节点（node）我们定义两个指标，road 为所走过的路径， res为该路径下的所能挖到宝藏的和
    res+= value_arr[node-1]     #每一次递归都要去对 res 和 road 进行一次更新
    road+=str(node)+" "

    for i in range(len(graph_arr[node-1])):   #对每一次父节点所能到达下一个子节点进行dfs
        if graph_arr[node-1][i] == 1:
            dfs(node+i+1,road,res)
        elif graph_arr[node-1][i] == 0:  #如果无路可走，则代表当前路径已经探索完，goal列表记录[res，road]
            goal.append([res,list(road)]) # 为了方便输出，我们直接list，用字符串拼接的方式是为了更好地记录路径

goal = []
for i in range(n):
    dfs(i+1,"",0)

maxum = 0
point = 0
for i in range(len(goal)):
    if goal[i][0] > maxum:  #找到最大值得储存的信息
        maxum = goal[i][0]
        point = i

for j in goal[point][1]:
    print(j,end="")    #输出
print("\r")
print(maxum)