AcWing 734. 能量石
原题链接
困难
作者:
今天AC了吗
,
2022-02-25 23:35:08
,
所有人可见
,
阅读 294
能量石
算法分析 (贪心 + dp)
贪心部分
- 对于最优方案的任意相邻的两个能量石i和j,贡献的能量总和为(假设t为之前的时间)
Ei - t * Li + Ej - (t + Si) * Lj
- 将i和j两个能量石交换,贡献的能量总数为
Ej - t * Lj + Ei - (t + Sj) * Li
- 交换后贡献总和不会变大,因此应满足
Ei - t * Li + Ej - (t + Si) * Lj >= Ej - t * Lj + Ei - (t + Sj) * Li
- 整理后得:
Si * Lj <= Sj * Li
将 i 的放在同一边即可得Si / Li <= Sj / Lj
- 因此以
Si / Li <= Sj / Lj
排序后的能量石,就能保证最优解在子序列中
dp部分
- dp数组的定义:
dp[i][j]
表示在前i个能量石中,耗时恰好为j得到的最大能量
- 01背包模型 可将空间降为一维
- dp数组的递推:情况一.不选当前的能量石能量为
dp[j]
; 情况二.选当前的能量石能量和为dp[j-s]+max(0,e-(j-s)*l)
- dp数组的初始化:dp[j] = 0 没吃能量石 能量为0
Python 代码
c = int(input())
for t in range(1,c+1):
n = int(input())
stone = []
m = 0
for i in range(n):
s,e,l = map(int,input().split())
m += s
stone.append([s,e,l])
stone = sorted(stone, key = lambda x: x[0] / max(x[2],1e-9)) #除数可能为0
dp = [0 for i in range(m+1)]
for s,e,l in stone:
for j in range(m,s-1,-1):
dp[j] = max(dp[j], dp[j-s]+max(0,e-(j-s)*l))
print(f"Case #{t}: {max(dp)}")