AcWing 10. 有依赖的背包问题-O(V)空间实现
原题链接
困难
作者:
change_5
,
2021-01-18 16:14:27
,
所有人可见
,
阅读 504
时间复杂度 O(NV^2)
参考文献
python 代码
N, V = [int(ss) for ss in input().split()]
tree = {}
nodes = [[]]
for _ in range(N):
v, w, p = [int(ss) for ss in input().split()]
if p == -1:
root = len(nodes)
else:
if p not in tree: tree[p] = []
tree[p].append(len(nodes))
nodes.append([v, w])
def dfs(root):
tmp_dp = [0 for _ in range(V+1)]
for child in tree.get(root, []):
child_dp = dfs(child)
v, w = nodes[child]
for ii in range(V, v-1, -1):
for jj in range(v, ii+1):
tmp_dp[ii] = max(tmp_dp[ii], child_dp[jj]+tmp_dp[ii-jj])
v, w = nodes[root]
for ii in range(V, v-1, -1):
tmp_dp[ii] = max(w, tmp_dp[ii-v]+w)
for ii in range(v): tmp_dp[ii] = 0
return tmp_dp
dp = dfs(root)
print(dp[-1])