题解 | #购物单#

inline1 = input().split(' ')
N = int(inline1[0])
m = int(inline1[1])

staffs = []
for i in range(m):
    inline2 = input().split(' ')
    v = int(inline2[0])
    p = int(inline2[1])
    q = int(inline2[2])
    staffs.append([v, p, q])

primes = {}
addts = {}
staffs_dict = {}

for i, ele in enumerate(staffs):
    staffs_dict[i] = ele

for k, v in staffs_dict.items():
    if not v[-1]:
        primes[k+1] = v[:-1]
    else:
        if v[-1] not in addts.keys():
            addts[v[-1]] = [v[:-1]]
        else:
            addts[v[-1]].append(v[:-1])

dp_arr = []
for av_num in range(1, len(primes)+1): 
    dp_arr.append([])
    for tens in range(1, N//10+1):
        dp_arr[-1].append(0)


for av_num in range(len(primes)):
    # print(av_num, primes)
    cur_staff = primes.popitem()
    idx = cur_staff[0]
    cur_prime = cur_staff[1]
    if idx in addts.keys():
        cur_addt = addts[idx]
        cur_comp = []
        if len(cur_addt) == 1:  # 对主从物品的多种可能组合进行建模
            cur_comp = [[cur_prime[0], cur_prime[0]*cur_prime[1]], 
                        [cur_prime[0]+cur_addt[0][0], cur_prime[0]*cur_prime[1]+cur_addt[0][0]*cur_addt[0][1]]]  # [[cur_prime], [cur_prime, cur_addt[0]]]
        elif len(cur_addt) == 2:  # 对主从物品的多种可能组合进行建模
            cur_comp = [[cur_prime[0], cur_prime[0]*cur_prime[1]], 
                        [cur_prime[0]+cur_addt[0][0], cur_prime[0]*cur_prime[1]+cur_addt[0][0]*cur_addt[0][1]], 
                        [cur_prime[0]+cur_addt[1][0], cur_prime[0]*cur_prime[1]+cur_addt[1][0]*cur_addt[1][1]], 
                        [cur_prime[0]+cur_addt[0][0]+cur_addt[1][0], cur_prime[0]*cur_prime[1]+cur_addt[0][0]*cur_addt[0][1]+cur_addt[1][0]*cur_addt[1][1]]]
    else:
        cur_comp = [[cur_prime[0], cur_prime[0]*cur_prime[1]]]
    for tens in range(N//10):
        cash = (1+tens)*10
        if tens > 0 and av_num > 0:  # dp_arr初始化，状态转移（比较大小）从初始化状态开始，初始化状态从左、上状态获得
            dp_arr[av_num][tens] = max(dp_arr[av_num][tens-1], dp_arr[av_num-1][tens])  # initialization
        elif tens > 0 and av_num == 0:  # dp_arr初始化，状态转移（比较大小）从初始化状态开始，初始化状态从左、上状态获得
            dp_arr[av_num][tens] = dp_arr[av_num][tens-1]  # initialization
        elif tens == 0 and av_num > 0:  # dp_arr初始化，状态转移（比较大小）从初始化状态开始，初始化状态从左、上状态获得
            dp_arr[av_num][tens] = dp_arr[av_num-1][tens]
        if av_num == 0:
            for comp in cur_comp:  # 对每一种主从组合，都进行一次01背包的状态转移
                # print(comp[0], cash)
                if comp[0] <= cash:
                    dp_arr[av_num][tens] = max(dp_arr[av_num][tens], comp[1])
        else:
            for comp in cur_comp:  # 对每一种主从组合，都进行一次01背包的状态转移
                if comp[0] == cash:
                    dp_arr[av_num][tens] = max(dp_arr[av_num][tens], comp[1])
                elif comp[0] < cash:
                    dp_arr[av_num][tens] = max(dp_arr[av_num][tens], dp_arr[av_num-1][(cash-comp[0])//10-1]+comp[1])
print(dp_arr[len(primes)-1][N//10-1])

01背包问题的拓展，如果对附属品和主物品同等级对待，那么就会在加入附属品时考虑是否已加入主物品，很麻烦。附属品可以看做是对某一个物品的升级，建模为该种物品的多种可能性，在dp时对每一种可能性都进行一次01背包问题的状态转移。这样就保证了附属品的加入在主物品加入的前提之下。