题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
class HJ16: def __init__(self): self.index = 0 self.v = [0] self.p = 0 self.q = 0 self.w = [0] self.next = [] T = input().split() N, m = int(T[0]), int(T[1]) ls_HJ16 = [] for i in range(m + 1): ls_HJ16_temp = HJ16() ls_HJ16.append(ls_HJ16_temp) ls_main = [] for i in range(1, m + 1): temp = input().split() ls_HJ16[i].index = i ls_HJ16[i].v[0] = int(temp[0]) ls_HJ16[i].p = int(temp[1]) ls_HJ16[i].q = int(temp[2]) ls_HJ16[i].w[0] = ls_HJ16[i].v[0] * ls_HJ16[i].p if ls_HJ16[i].q != 0: ls_HJ16[ls_HJ16[i].q].next.append(i) else: ls_main.append(i) ii = 1 for i in ls_main: ls_HJ16[i].index = ii ii += 1 next0v, next0w, next1v, next1w = 0, 0, 0, 0 if len(ls_HJ16[i].next) != 0: next0v = ls_HJ16[ls_HJ16[i].next[0]].v[0] next0w = ls_HJ16[ls_HJ16[i].next[0]].w[0] ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next0v) ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next0w) if len(ls_HJ16[i].next) == 2: next1v = ls_HJ16[ls_HJ16[i].next[1]].v[0] next1w = ls_HJ16[ls_HJ16[i].next[1]].w[0] ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next1v) ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next1w) ls_HJ16[i].v.append(ls_HJ16[i].v[0] + next0v + next1v) ls_HJ16[i].w.append(ls_HJ16[i].w[0] + next0w + next1w) dp = [[0] * (N // 10 + 1) for _ in range(len(ls_main) + 1)] # dp=[[0]*(N+1)]*(len(ls_main)+1) for i in [0] + ls_main: for j in range(N // 10 + 1): max_dp = dp[ls_HJ16[i].index - 1][j] for k in range(len(ls_HJ16[i].v)): if j >= ls_HJ16[i].v[k] // 10: max_dp = max( max_dp, dp[ls_HJ16[i].index - 1][j - ls_HJ16[i].v[k] // 10] + ls_HJ16[i].w[k], ) dp[ls_HJ16[i].index][j] = max_dp print(dp[len(ls_main)][N // 10])