※ 引述《sustainer123 (caster )》之铭言：
: ※ 引述《oin1104 (是oin的说)》之铭言：
: : 题目翻译：
: : 有一堆书 给你他们的宽跟高
: : 跟一个宽shelfWidth的书架
: : 每次放书都要照顺序垂直放进去
: : 不可以叠在一起
: : 放满了就放个隔板 然后去下一层放
: : 请问最少要多少高度的书架才能装下所有书
: : 思路：
: : 我原本没看到要找顺序
: : 所以就sort然后从大赛到小
: : 干咧
如果没要求顺序的话是 NP-complete
给定一个阵列 A[1..n]
把 shelfWidth 设为 sum(A[1..n])/2
且 n 本书的高度都设 1、宽度是 A[i]
则答案是 2 若且唯若存在 subset 的和恰等于 shelfWidth
所以可以 reduce 成 partition problem
不过 constraint 里 shelfWidth 最大只有 1000 就是了
:)