题解 | #购物单#

x = input()
N, m = x.split(' ')
N, m = int(N), int(m)

price, weight, q_type, score = list(), list(), list(), list()
for i in range(m):
    v, w, a = input().split(' ')
    v, w, a = int(v), int(w), int(a)
    price.append(v)
    weight.append(w)
    q_type.append(a)
    score.append(v * w)

all_items = dict()
for _ in range(m):
    if q_type[_] == 0:
        if _ not in all_items:
            all_items[_] = {
                'price': price[_],
                'happy': score[_],
                'more': []
            }
    elif q_type[_] > 0:
        item = q_type[_] - 1
        if item in all_items:
            tmp = {
                'price': price[_] + all_items[item]['price'],
                'happy': score[_] + all_items[item]['happy']
            }
            all_items[item]['more'].append(tmp)
            if len(all_items[item]['more']) > 1:
                pre = all_items[item]['more'][0]
                tmp = {
                    'price': pre['price'] + price[_],
                    'happy': pre['happy'] + score[_]
                }
                all_items[item]['more'].append(tmp)
        else:
            all_items[item] = {
                'price': price[item],
                'happy': score[item],
                'more': []
            }
            tmp = {
                'price': price[_] + all_items[item]['price'],
                'happy': score[_] + all_items[item]['happy']
            }
            all_items[item]['more'].append(tmp)

it = list()
for tmp in all_items.keys():
    it.append(tmp)

def get_base(price):
    b = False
    for base in [1000, 100]:
        for _ in price:
            if _ % base != 0:
                b = False
                break
            b = True
        if b:
            return base
    return 10

base = get_base(price)
k = int(N / base)
l = len(it)
f = [[0] * (k+1) for _ in range(l+1)]

for i in range(1, l+1):
    for j in range(1, k+1):
        p = j * base
        item = all_items[it[i-1]]
        if item['price'] > p:
            f[i][j] = f[i-1][j]
        else:
            tmp = list()
            tmp.append(max(f[i-1][j], f[i-1][j - int(item['price'] / base)] + item['happy']))
            if len(item['more']):
                for sb in item['more']:
                    if sb['price'] <= p:
                        tmp.append(max(f[i-1][j], f[i-1][j - int(sb['price'] / base)] + sb['happy']))
            f[i][j] = max(tmp)

print(f[l][k])