题解 | #购物单#

n, m = map(int,input().split())
temp = [[] for _ in range(m+1)]
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z == 0:
        temp[i] = [x//10,y] + temp[i]
    else:
        temp[z]+= [x//10,y]
temp = list(filter(None, temp))
n = n//10
dp = [0] * (n + 1)
for x in temp:
    for y in range(n,-1,-1):
        price = x[0]
        value = x[1]
        #只有主键
        if y>=price:
            dp[y] = max(dp[y], dp[y-price]+price*value)
        #只有主键+一个键
        if len(x) >= 4:
            price2 = x[0] + x[2]
            if y>=price2:
                dp[y] = max(dp[y], dp[y-price2]+x[0]*x[1] + x[2]*x[3])
        #只有主键+两个键
        if len(x) == 6:
            price3 = x[0] + x[4]
            if y>=price3:
                dp[y] = max(dp[y], dp[y-price3]+x[0]*x[1] + x[4]*x[5])
            price4 = x[0] + x[4] + x[2]
            if y>=price4:
                dp[y] = max(dp[y], dp[y-price4]+x[0]*x[1] + x[4]*x[5]+ x[2]*x[3])  
print(max(dp)*10)

好烦，希望碰不到