关於这题的解法 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1597811597.A.CDC.html