#16095: 關於這一題的測資


rollfc (點石學園 StoneCampus)


這個題目乍看之下是01背包問題,但是礙於記憶體上限只能用一維陣列更新

但是題目的說明中有提到 overflow 導致戰鬥力的問題,這也是這個題目的變化處

請嘗試以下的側資就能理解 overflow 導致的情況:

3

699999 2 699999

---------------------

700000

答案是700000,是因為把三個題目都完成,而完成前兩個時因為overflow 導致 戰鬥力單位是1時被更新了

換句話說這一題無法只靠著一維陣列反向更新的方式去處理01背包問題,而是要順向從戰鬥力1開始更新,

但要怎麼解決更新到不該更新的情況就得想辦法(請參考PTT C和C++版)