這個題目乍看之下是01背包問題,但是礙於記憶體上限只能用一維陣列更新
但是題目的說明中有提到 overflow 導致戰鬥力的問題,這也是這個題目的變化處
請嘗試以下的側資就能理解 overflow 導致的情況:
3
699999 2 699999
---------------------
700000
答案是700000,是因為把三個題目都完成,而完成前兩個時因為overflow 導致 戰鬥力單位是1時被更新了
換句話說這一題無法只靠著一維陣列反向更新的方式去處理01背包問題,而是要順向從戰鬥力1開始更新,
但要怎麼解決更新到不該更新的情況就得想辦法(請參考PTT C和C++版)