题解 | 购物单

import sys
from collections import defaultdict
n,m=map(int,sys.stdin.readline().strip().split())
items=[list(map(int,sys.stdin.readline().strip().split())) for _ in range(m)]
main_items=[]
g=defaultdict(list)
for i in range(m):
    v,w,q=items[i][0],items[i][1],items[i][2]
    if q==0:
        main_items.append([i,v,w])
    else:
        g[q-1].append([v,w])
m1=len(main_items)
dp=[[0]*(n//10+1) for _ in range(m1+1)]
for ii in range(1,m1+1):
    i,v,w=main_items[ii-1][0],main_items[ii-1][1],main_items[ii-1][2]
    if not g[i]: # 没有附件
        v1=w1=v2=w2=0
    elif len(g[i])==1: # 一个附件
        v1=w1=0
        v2,w2=g[i][0][0],g[i][0][1]
    else: # 两个附件
        if g[i][0][0]<g[i][1][0]:
            v1,w1=g[i][0][0],g[i][0][1]
            v2,w2=g[i][1][0],g[i][1][1]
        else:
            v2,w2=g[i][0][0],g[i][0][1]
            v1,w1=g[i][1][0],g[i][1][1]
    for j in range(n//10+1):
        # 不能放当前物品，承接上一行的最大值
        if j<v//10:  
            dp[ii][j]=dp[ii-1][j]
        # 只能放当前物品+0个附件，不放vs放最大值
        elif v//10<=j<v//10+v1//10: 
            dp[ii][j]=max(dp[ii-1][j],dp[ii-1][j-v//10]+v*w)
        # 可放当前物品+较小的附件，不放vs放主件vs放主件+附件1
        elif v//10+v1//10<=j<v//10+v2//10: 
            dp[ii][j]=max(dp[ii-1][j],dp[ii-1][j-v//10]+v*w,dp[ii-1][j-v//10-v1//10]+v*w+v1*w1)
        # 可放当前物品+较小/大附件，不放vs放主件vs放主+附1vs放主+附2
        elif v//10+v2//10<=j<v//10+v1//10+v2//10: 
            dp[ii][j]=max(dp[ii-1][j],dp[ii-1][j-v//10]+v*w,dp[ii-1][j-v//10-v1//10]+v*w+v1*w1,dp[ii-1][j-v//10-v2//10]+v*w+v2*w2)
        # 可放当前物品+较小+较大附件，不放vs放主件vs放主+附1vs放主+附2vs放主+附1+附2
        elif j>=v//10+v1//10+v2//10:
            dp[ii][j]=max(dp[ii-1][j],dp[ii-1][j-v//10]+v*w,dp[ii-1][j-v//10-v1//10]+v*w+v1*w1,
dp[ii-1][j-v//10-v2//10]+v*w+v2*w2,dp[ii-1][j-v//10-v1//10-v2//10]+v*w+v1*w1+v2*w2)
print(dp[-1][-1])