Acwing：挖地雷（DP Python）

有地图n 个地窖（n≤200)每个地窖定数量的地雷。

同时，给出地窖之间的连接路径，并规定路径是单向的，并确保小地窖指向大地窖，没有路径可以通过几个地窖返回原地窖。

有人可以从任何地方挖掘地雷，然后沿着指定的连接挖掘（只选择一条路径），当没有连接时挖掘地雷。

设计一个挖地雷的方案，让他能挖到最多的地雷。

注意：只有一条路线可以路线可以挖到最多的地雷。

输入格式

第一行包含整数n，表示地窖的数量。

第二行包括n个整数，依次是每个地窖地雷的数量。

接下来，每行包含两个整数xi,yi，表示从xi可到yi，xi

最后一行为0表示结束。

输出格式

第一行表示挖掘最多地雷时挖掘地雷的顺序，各地窖序号之间以‘-’分隔，如:k1?k2?…?kv。

第二行包含一个整数，表示能挖到的地雷最多。

输入样例：

6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0 

输出样例：

3-4-5-6 34

思路 ：

两个循环dp即可 请看注释

 n = int(input()) lst = [0]   list(map(int,input().split())) # 每个节点的地雷数 Map = [[0 for i in range(n 1)]for j in range(n 1)] # 连通性 before = [0 for i in range(n 1)] # 存储每个节点的前驱节点 dp = [0 for i in range(n 1)] din = [0 for i in range(n 1)] # 入度为0的点dp值已经确定 mx = 0 # 最大值 last_node = 0 # 最后一个节点  def Print(node,lst) : # 打印结果     if lst[node] == 0 :         print(node,end='')         return     Print(lst[node],lst)     print('-' str(node),end='')  while 1 :     a,b = map(int,input().split())     if a == 0 and b == 0 :         break     Map[a][b] = 1     din[b]  = 1      for i in range(1,n 1) :     if din[i] == 0 :         dp[i] = lst[i]          for i in range(1,n 1) :     for j in range(i 1,n 1) :         if Map[i][j] :             tmp = lst[j]   dp[i]             if tmp > dp[j] : # 如果新值比原值大                 dp[j] = tmp # 更新dp值                 before[j] = i # 更新前驱节点         if dp[j] > mx :              last_node = j  # 只在当前点dp大于已有mx的时候 更新最后一个节点         mx = max(mx,dp[j])              Print(last_node,before) print() print(mx)