#22617: 背包非背包


p3a_owhj (阿普二信)


題目說是背包問題,但不知道可使用 什麼「變形」方式的背包 可解,好像會 TLE吧

但 2^0+2^1+...+2^m-1 < 2^m
若將重量的級數看成 0~m級,每次將最小的兩個同級價值合併,  重量升一級,當到達m級時,價值最大的 m級就是答案了

我是用 priority_queue 實作的,勉強 AC

另最後一個測資 > 9*10^9

#22632: Re:背包非背包


asnewchien@gmail.com (david)


感謝您的想法,

應該不必使用 priority_queue

只要把每個等級的值排序後兩兩相加,丟到下一級即可。

#41088: Re: 背包非背包


seancai78@gmail.com (風月春秋)


另最後一個測資 > 9*10^9


超級感謝測資提示,不然我不知道甚麼時候才能發現