【Kickstart】2019 Round B - Energy Stones

解法

乍一看，如果是搜索的题，要枚举所有吃的顺序，那应该是

O(n!)

复杂度，估计吃不消

所以得往DP方向考虑，那么就有点像01背包问题，能量是物品的价值，而背包大小则是所有石头食用时间的总和

但是跟01背包问题不同的是，最后的能量和吃的顺序有关，而01背包里最后的能量跟物品放进背包的顺序无关，所以能拆解成子问题

想了半天也不会做

看完解答之后很有启发，对于这种跟顺序有关的情况，如果给定任何一个石头集合，我们都能排好一个顺序使得价值最大

那么先排序再做01背包就行了

这样，在决定物品i放不放的时候，背包里只需要考虑那些装入了应该排在它前面的物品的情况

对于大数据集来说，假如物品i和j相邻，分析可知它们谁排前面只取决于

S

和

L

， S L \frac{S}{L} LS​更大的应该排前面，而对于

L=0

的那些石头，它们的 S L \frac{S}{L} LS​则取无穷大值

#!/usr/bin/env python
# -*- coding: utf-8 -*-

MOD = 10**9+7
import functools

S,E,L = [],[],[]

def cmp(i,j):
    global S,E,L
    if S[i]*L[j]<S[j]*L[i]:
        return -1
    if S[i]*L[j]>S[j]*L[i]:
        return 1
    return 0

if __name__ == '__main__':
    t = int(input())
    for _ in range(1, t + 1):
        n = int(input())
        S, E, L = [], [], []
        for i in range(n):
            s,e,l = map(int,input().split())
            S.append(s)
            E.append(e)
            L.append(l)
        rank = list(sorted(range(n),key=functools.cmp_to_key(cmp)))
        T = sum(S)
        f = [0]*(T+1)
        for i in range(n):
            for t in range(T,S[rank[i]]-1,-1):
                eatTime = t-S[rank[i]]
                energy = max(E[rank[i]]-L[rank[i]]*eatTime,0)
                if energy>0:
                    f[t] = max(f[t],f[t-S[rank[i]]]+energy)
        print("Case #{}: {}".format(_, max(f)))