题解 | 购物单

from re import I
import sys
import random

n,m = sys.stdin.readline().strip().split()
n=int(n)
n //= 10 #优化运算
m=int(m)
worth={}
weight={}
annex={}
main_part={}
for index in range(1,m+1):
    worth[index],weight[index],annex[index] = sys.stdin.readline().strip().split()
    worth[index]=int(worth[index])
    worth[index] //= 10
    weight[index]=int(weight[index])    
    annex[index]=int(annex[index])
#print(annex)
for j in range(1,m+1):
    if annex[j] == 0:
        main_part[j]=annex[j]
        del annex[j]
attachments={}
for i in main_part.keys():
    attachments[i]=[]
    for j in annex.keys():
        if annex[j] == i:
            attachments[i].append((worth[j],weight[j]))

#print(attachments)

dp = [0] * (n + 1)
#选择主件
for  i in main_part.keys():
    #从后往前遍历，避免重复选择
    for j in range(n, worth[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - worth[i]] + worth[i] * weight[i])
        #计算附件
        if len(attachments[i]) > 0:
            for av, ap in attachments[i]:
                if j >= worth[i] + av:
                    dp[j] = max(dp[j], dp[j - worth[i] - av] + worth[i] * weight[i] + av * ap)
            if len(attachments[i]) == 2:
                av1, ap1 = attachments[i][0]
                av2, ap2 = attachments[i][1]
                if j >= av1 + av2 + worth[i]:
                    dp[j] = max(dp[j], dp[j - worth[i] - av1 - av2] + worth[i] * weight[i] + av1 * ap1 + av2 * ap2)
 
print(dp[n]*10)