题解 | 购物单

import sys
budget,s = map(int,input().split())
desk = [list(map(int,line.split())) for line in sys.stdin]

# 构建新列表，取附件的情况
primary={}
# 表结构
# primary={priv_index:[sub1,sub2]}
for i in range(s):
    priIndex = desk[i][2]-1
    if priIndex ==-1:
        # 主键
        primary[i] = primary.get(i,[]) # 如果i不在primary中，增加
    else:
        # 说明是附件
        primary[priIndex] = primary.get(priIndex,[]) + [i]
# 构建新列表，区分有附件的和没有附件的情况
nosub = []
hassub = []
for i in primary.keys():
    if primary[i] ==[]:
        nosub.append(i)
    else:
        hassub.append(i)

fullgoods = nosub+hassub

# 构建dp数组，
k = 10 # 先考虑简单情况，再算能被100等更大的数整除的情况
m = int(budget/k)
n = len(fullgoods)

dp = [[0]*(m+1) for _ in range(n+1)]

def primary_and_sub_list(i:int):
    # 逻辑是每个物品返回
    # 输入物品的index
    # 用于返回一个有附件物品的情况组合列表
    # 当前物品含有附件，分四种情况         
    # 1.只有主件
    # 2.主件+附件1
    # 3.主件+附件2
    # 4.主件+ 附件1+附件2
    # 取几种情况的最大值
    # now = desk[i]
    price0,value0 = desk[i][0],desk[i][0]*desk[i][1]
    subgoods = [desk[j] for j in primary[i]]
    value = [value0]
    price = [price0]
    while subgoods:
        k = subgoods.pop()
        price.append(k[0]+price0)
        value.append(k[0]*k[1]+value0)
        for u in subgoods:
            price.append(u[0]+k[0]+price0)
            value.append(u[0]*u[1]+k[0]*k[1]+value0)
    #print(price,value)
    return price,value

# 填表：
for i in range(1,n+1):
    for j in range(1,m+1):# 每次多k元
        goodIndexi = fullgoods[i-1]# dp列表多了0行
        if goodIndexi in hassub:
            pricelist,valuelist = primary_and_sub_list(goodIndexi)
            solution = [dp[i-1][j]]
            for pricei,valuei in zip(pricelist,valuelist):
                if pricei <= j*k:
                # 能放下
                    addthis = dp[i-1][j-int(pricei/k)]+valuei # 放此物品
                    # notadd = dp[i-1][j] # 不放
                    solution.append(addthis)
            dp[i][j]=max(solution)
        else:
            # 不含附件
            pricei = desk[goodIndexi][0]
            value = desk[goodIndexi][0]*desk[goodIndexi][1]
            if pricei <= j*k:
                # 能放下
                addthis = dp[i-1][j-int(pricei/k)]+value # 放此物品
                notadd = dp[i-1][j] # 不放
                dp[i][j] = max(addthis,notadd)
            else:
                # 不能放下
                dp[i][j]=dp[i-1][j]

print(dp[-1][-1])