#22617: 背包非背包


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [210.71.40.107]
最後登入時間 :
2024-03-29 10:41:11
c835. 第六題:背包問題 -- 2018資訊學科能力競賽高中組高雄市 | From: [36.225.44.28] | 發表日期 : 2020-09-20 02:46

題目說是背包問題,但不知道可使用 什麼「變形」方式的背包 可解,好像會 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)

學校 : 不指定學校
編號 : 68108
來源 : [1.168.27.172]
最後登入時間 :
2024-04-24 20:07:19
c835. 第六題:背包問題 -- 2018資訊學科能力競賽高中組高雄市 | From: [122.118.83.198] | 發表日期 : 2020-09-21 02:15

感謝您的想法,

應該不必使用 priority_queue

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

 
ZeroJudge Forum