题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
capacity,n=map(int,input().strip().split())
master={}
slave={}
for i in range(1,n+1):
w,factor,flag=map(int,input().split())
w//=10
if flag==0:
master[i]=(w,w*factor)
else:
if flag not in slave:
slave[flag]=[(w,w*factor)]
else:
slave[flag].append((w,w*factor))
dp=[[0]*(capacity//10+1) for i in range(len(master)+1)]
keys=list(master.keys())
for i in range(1,len(master)+1):
for j in range(1,capacity//10+1):
dp[i][j]=dp[i-1][j]
if master[keys[i-1]][0]<=j:
dp[i][j]=max(dp[i][j],master[keys[i-1]][1]+dp[i-1][j-master[keys[i-1]][0]])
if keys[i-1] in slave and slave[keys[i-1]][0][0]+master[keys[i-1]][0]<=j:
dp[i][j]=max(dp[i][j],dp[i-1][j-slave[keys[i-1]][0][0]-master[keys[i-1]][0]]+master[keys[i-1]][1]+slave[keys[i-1]][0][1])
if keys[i-1] in slave and len(slave[keys[i-1]])==2:
if slave[keys[i-1]][1][0]+master[keys[i-1]][0]<=j:
dp[i][j]=max(dp[i][j],dp[i-1][j-slave[keys[i-1]][1][0]-master[keys[i-1]][0]]+slave[keys[i-1]][1][1]+master[keys[i-1]][1])
if slave[keys[i-1]][0][0]+slave[keys[i-1]][1][0]+master[keys[i-1]][0]<=j:
dp[i][j]=max(dp[i][j],dp[i-1][j-slave[keys[i-1]][0][0]-slave[keys[i-1]][1][0]-master[keys[i-1]][0]]+slave[keys[i-1]][0][1]+slave[keys[i-1]][1][1]+master[keys[i-1]][1])
print(dp[len(master)][capacity//10]*10)
