#16095: 關於這一題的測資


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間 :
2024-11-10 10:25:04
b568. 70萬都沒有,你還想當選手? -- 104學年度板橋高中校內資訊學科能力競賽(四) | From: [114.34.219.44] | 發表日期 : 2018-11-19 03:32

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

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

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

3

699999 2 699999

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

700000

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

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

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

 
ZeroJudge Forum