作者sophialiege ()
看板ACMCLUB
標題Re: [問題] 10690
時間Sat Jul 23 00:38:32 2005
※ 引述《DJWS (...)》之銘言：
: ※ 引述《sophialiege ()》之銘言：
: : 我不記得我以前是怎麼寫的
: : 不過我現在有個點子
: : 這一題正常的DP要二維table是吧
: : 可是他有一個維度最多只有50
: : 再考慮你的DP方式,是不是很合適用bitwise operation
: : (long long 有 64 bits)
: : 接下來算複雜度=> 5000*100*110 這樣要過應該 ok
: 謝謝你 我看懂了你的方法 (這還是我第一次用bit來存資訊...挺有趣的)
: 也寫出來了 :)
: 我是將一個數目 將可以湊成這個數目的數字個數 以bit的方式存在表格中
: 如此便可以將所有情形都列舉在一條陣列裡面
: 然後檢驗全部的情形 便可以求出解
: 我覺得這一題用bit來存放資訊 同時也壓縮了時間複雜度
: 若不用bitwise operation 鐵定會超時的 而且也會浪費很多記憶體空間
: 是否有更好的方法呢?
我剛剛也用同樣的方法寫了一遍
只要0.4s就A了 rank 9 應該算不錯的方法了吧
或許你想看一下我的code比較一下你慢在哪
http://www.csie.ntu.edu.tw/~b91089/10690
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.225.209.171