题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
money,length = map(int,input().split()) money //= 10 goods = dict() for i in range(1,length+1): v,p,q = map(int, input().split()) v //= 10 if q == 0: if i not in goods.keys(): goods[i] = [[v, v*p], [0, 0], [0, 0]] else: goods[i][0] = [v, v*p] else: if q not in goods.keys(): goods[q] = [[0, 0], [v, v*p], [0, 0]] elif goods[q][1] == [0, 0]: goods[q][1] = [v, v*p] else: goods[q][2] = [v, v*p] dp = [0]*(money+1) for k,v in goods.items(): for j in range(money ,v[0][0]-1 ,-1): dp[j] = max(dp[j],dp[j-v[0][0]] + v[0][1]) if j >= v[0][0]+v[1][0]: dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]] + v[0][1]+v[1][1]) if j >= v[0][0]+v[2][0]: dp[j] = max(dp[j],dp[j-v[0][0]-v[2][0]] + v[0][1]+v[2][1]) if j >= v[0][0]+v[1][0]+v[2][0]: dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]-v[2][0]] + v[0][1]+v[1][1]+v[2][1]) print(dp[money] * 10)
