#20893: python 的同學


m80126colin (許胖)

School : 新北市立板橋高級中學
ID : 2331
IP address : [35.203.227.81]
Last Login :
2020-12-25 10:47:06
d390. 00562 - Dividing coins -- UVa562 | From: [219.71.18.160] | Post Date : 2020-03-17 03:24

此題可將 constraint 看成,存在一個大小為 sum(mi) / 2 的背包,因為物件的重量與價值是同個維度,重複使用會造成浪費,不如將背包內記錄 True、False,如此不難看出當背包存儲 boolean 後,可使用位元運算加速:

dp |= dp << mi

 
ZeroJudge Forum