網頁

2014年4月24日 星期四

POJ 1014 Dividing

題意:
    每次有n1,n2,n3,n4,n5,n6六個數字代表價值1的大理石有n1個,價值2的大理石有n2個,....,價值6的大理石有n6個,現在要將這些大理石分成兩堆,問能否使得這兩堆價值一樣?

想法:
    背包問題,一開始單純把價值i的大理石做了ni次,例如價值5有70個,for迴圈就跑70次,結果就TLE了。
    後來學到其實可以將70 = 1+2+4+8+16+32+7,也就是ni=1+2+4+8+....+2^x+left,這樣可以大大減少for的次數,ni如果是70只要做6+7=13次。


沒有留言:

張貼留言