PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] ZeroJudge-c271 疊疊樂(Easy)

看板Prob_Solve (計算數學 Problem Solving)作者fatcat8127 (胖胖貓)時間4年前 (2020/08/19 12:33)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/1

關於這題的解法 tag 其實已經寫明：動態規劃+排序。這類型的題目都會有更新順序的問題所以必須事先排序但問題就在於排序的規則。首先題目要求箱子疊起來時『長度』必須呈非嚴格遞增，所以長度為排序時的首要考量，更新時應該由小到大，但是對於相同長度時的物品該怎麼考慮？題目提到箱子有負重限制，疊在某個箱子上面的重量加上自己不能超過該箱子的最大負重。正確答案是當長度相同時再依據負重限制小到大排序。但我考量是先依據額外負重限制(題目給的S-W)小到大相同時在考慮箱子的重量，不過被 vincnet 光速打臉，附上打臉測資： 4 1 7 5 10 3 8 1 6 直覺理解是(1) 額外負重限制越小(S-W)的應該越優先更新 (2) 箱子重量越輕(W)的應該越優先更新但無法理解的點在於如何將(1)(2)併在一起討論，顯然(1)(2)會相互影響。對於排序條件無法獨立討論(決定哪個先後)，我目前想到的類似題是 UVa10026 - Shoemaker's Problem，不過這題可以透過代數+貪婪法證明。不知道怎麼套用到這題上面...作為證明? 總不是說像撒尿牛丸全部加一起就好... -- 精彩不亮麗, 起落是無常 https://images.app.goo.gl/3nensFSnV52DCKet9 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.222.86.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1597811597.A.CDC.html