题解 | 购物单

from collections import defaultdict
n,m = map(int,input().split())
n//=10
value = []
weight = []
l0 = []
dict1 = defaultdict(list)
for i in range(m):
    v,w,q = map(int,input().split())
    v //= 10
    value.append(v*w)
    weight.append(v)
    if q == 0:
        l0.append(i)
    else:
        dict1[q-1].append(i)
dp = [0]*(n+1)
for j in range(m):
    for w in reversed(range(n+1)):
        if j in l0:
            if len(dict1[j])==0:
                if w>=weight[j]:
                    dp[w] = max(dp[w],dp[w-weight[j]]+value[j])
            elif len(dict1[j])==1:
                a = dict1[j][0]
                if weight[a]+weight[j]>w>=weight[j]:
                    dp[w] = max(dp[w],dp[w-weight[j]]+value[j])
                elif w >= weight[a]+weight[j]:
                    dp[w] = max(dp[w],dp[w-weight[j]]+value[j],dp[w-weight[j]-weight[a]]+value[j]+value[a])
            else:
                a,b = dict1[j][0],dict1[j][1]
                if weight[a] > weight[b]:
                    a,b = b,a
                if weight[a]+weight[j]>w>=weight[j]:
                    dp[w] = max(dp[w], dp[w - weight[j]] + value[j])
                elif weight[b]+weight[j]>w>=weight[j]:
                    dp[w] = max(dp[w], dp[w - weight[j]] + value[j],dp[w - weight[j] - weight[a]] + value[j] + value[a])
                elif weight[a]+weight[b]+weight[j]>w>=weight[j]:
                    dp[w] = max(dp[w], dp[w - weight[j]] + value[j],
                                dp[w - weight[j] - weight[a]] + value[j] + value[a],
                                dp[w - weight[j] - weight[b]] + value[j] + value[b])
                elif w >= weight[a]+weight[b]+weight[j]:
                    dp[w] = max(dp[w], dp[w - weight[j]] + value[j],
                                dp[w - weight[j] - weight[a]] + value[j] + value[a],
                                dp[w - weight[j] - weight[b]] + value[j] + value[b],
                                dp[w - weight[j] - weight[a] - weight[b]] + value[j] + value[a] + value[b])
print(dp[n]*10)