题解 | #购物单#

import sys
import collections
import functools


n,m=map(int,input().strip().split())
v=[0]*m    #价格    均默认为0
p=[0]*m    #重要性
q=[0]*m    #编号

d=collections.defaultdict(list) #键值为主键编号，内容为附件的编号
for i in range(m):
    all=list(map(int,input().strip().split()))
    v[i]=all[0]     #价格
    p[i]=all[1]     #重要性
    q[i]=all[2]-1   #编号     #注意用例，用例的编号从1开始，而我们字典的编号从0开始
    if q[i] != -1:
        d[q[i]].append(i)  

dn=collections.defaultdict(list)  #状态转移：有附件的主件+主件加一个附件+主件加两个附件+没有附件的主件
for i in d.keys():
    dn[i].append(
        [
            v[i],   #主件价格
            v[i]*p[i]     #满意度
            ]
            )
    for j in d[i]:
        dn[i].append(
            [
                v[j]+v[i],     #主件加上其中一个附件的价格       
                v[j]*p[j]+v[i]*p[i]    #主件加上其中一个附件的满意度
                ]
                )
    if len(d[i])==2:      #如果某个主件有两个附件
        dn[i].append(
            [
                v[d[i][0]] + v[i] + v[d[i][1]],         #主件加上两个附件的价格
                v[d[i][0]]*p[d[i][0]] + v[i]*p[i] + v[d[i][1]]*p[d[i][1]]  #主件加上另外两个附件的满意度
            ]
            ) 
for i in range(m):
    if i not in d and q[i]==-1:
        dn[i].append(
            [
                v[i],       #主件的价格
                v[i]*p[i]   #主件的满意度
            ]
            )

@functools.cache
def f(i,n):
    if n<0:
        return 0
    if i<0:
        return 0
    res=f(i-1,n)
    for v,p in dn[k[i]]:
        if v > n:
            continue
        res=max(res,f(i-1,n-v)+p)
    return res

k=list(dn.keys())   #把状态转移出来的表，键值取出来作为一个表格
print(f(len(k)-1,n))