#28996: 解題思路


az07260906 (呢嗎嗎)

學校 : 不指定學校
編號 : 125438
來源 : [61.224.2.106]
最後登入時間 :
2022-01-22 18:31:27
c471. apcs 物品堆疊 (Stacking) -- apcs | From: [36.232.209.227] | 發表日期 : 2022-01-21 13:14

這題有點像是排序法的延伸,比如說有三個箱子,由上而下是s[0]、s[1]、s[2],w[0] = 3、w[1] = 4、w[2] = 5,h[0] = 1、h[1] = 2、h[3] = 3。而因為在單獨討論兩個相鄰箱子耗能的情況下,放在他們上面或下面的那一個箱子他耗能在不同情況下都不會有任何改變,所以可以先單獨比較兩個箱子在不同情況下的耗能差,如果不符合最小耗能的情況再做交換。

那我們來討論實際情況,先比較s[0]、s[1],當3公斤物體放在上面的情況下,所需耗能是w[0] X h[1] = 6。而在4公斤物體放上面的情況下,所需耗能是w[1] X h[0] = 4,所以在比較下,4公斤物體放上面比較好,所以兩者做swap的動作。以此類推,之後再比較s[1]、s[2],在比較s[0]、s[1]。

之後排完後的情況會是由上而下s[0]、s[1]、s[2],w[0] = 5、w[1] = 4、w[2] = 3,h[0] = 3、h[1] = 2、h[3] = 1。那我們要怎麼算出最小總耗能呢?便是w[0] X h[1] + (w[0] + w[1]) X h[2]。

如果假設現在有4個物品好了,所需總耗能便是w[0] X h[1] + (w[0] + w[1]) X h[2] + (w[0] + w[1] + w[2]) X h[3],以此類推,5個便是w[0] X h[1] + (w[0] + w[1]) X h[2] + (w[0] + w[1] + w[2]) X h[3] + (w[0] + w[1] + w[2] + w[3]) X h[4]。這樣應該就能抓到規律了八。可以先設一個sum計算總重量喔,初始值為0,會隨著迴圈變大。接下來就自己想瞜~

 

 
 
ZeroJudge Forum