【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)))