题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
N, m = map (int, input().split())
main, aux = {}, {}
N = int(N/ 10)
for i in range(1, m + 1):
v, p, q = map(int, input().split())
v = int(v/10)
if q == 0:
main[(i, 0)] = (v, p*v)
else:
if (q, 0) not in aux:
aux[(q, 0)] = (v, p*v)
else:
aux[(q, 1)] = (v, p*v)
for i in range(1, m + 1):
if (i, 0) in aux:
if (i, 0) in aux:
if (i, 1) in aux:
main[(i, 1)] = (main[(i, 0)][0] + aux[(i, 0)][0], main[(i, 0)][1] + aux[(i, 0)][1])
main[(i, 2)] = (main[(i, 0)][0] + aux[(i, 1)][0], main[(i, 0)][1] + aux[(i, 1)][1])
main[(i, 3)] = (main[(i, 0)][0] + aux[(i, 0)][0] + aux[(i, 1)][0], main[(i, 0)][1] + aux[(i, 0)][1] + aux[(i, 1)][1])
else:
main[(i, 1)] = (main[(i, 0)][0] + aux[(i, 0)][0], main[(i, 0)][1] + aux[(i, 0)][1])
dp = [[0] * (N + 1) for _ in range(m+2)]
for i in range(1, m + 1):
dp[i][0] = 0
for j in range(1, N + 1):
if (i,3) in main:
temp = 0
dpmax = 0
for k in range(4):
if j >= main[(i, k)][0]:
temp = max(dp[i-1][j], dp[i-1][j-main[(i, k)][0]] + main[(i, k)][1])
else:
temp = dp[i-1][j]
dpmax = max(dpmax, temp)
dp[i][j] = dpmax
elif (i,1) in main:
temp = 0
dpmax = 0
for k in range(2):
if j >= main[(i, k)][0]:
temp = max(dp[i-1][j], dp[i-1][j-main[(i, k)][0]] + main[(i, k)][1])
else:
temp = dp[i-1][j]
dpmax = max(dpmax, temp)
dp[i][j] = dpmax
elif (i,0) in main:
if j >= main[(i, 0)][0]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-main[(i, 0)][0]] + main[(i, 0)][1])
else:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
# print(i,j, dp[i][j])
print(dp[m][N] * 10)
