AcWing 734. 能量石(Python)
原题链接
困难
作者:
习学学
,
2021-02-08 22:47:40
,
所有人可见
,
阅读 363
Python 代码
T = int(input())
case = 1
while T:
T -= 1
n = int(input())
stones = []
m = 0
for i in range(n):
s, e, l = map(int, input().split())
if l == 0: rate = float('inf')
else: rate = s/l
m += s
stones.append([rate, s, e, l])
stones.sort()
dp = [-float('inf')] * (m+1)
dp[0] = 0
for _, s, e, l in stones:
for j in range(m, s-1, -1):
dp[j] = max(dp[j], dp[j-s] + e - (j-s)*l)
res = 0
for tmp in dp:
res = max(res, tmp)
print('Case #'+ str(case) + ': ' + str(res))
case += 1