※ 引述《sophialiege ()》之铭言： : ※ 引述《DJWS (...)》之铭言： : : 恩 讨论版很多人说这一题可以用 0/1 knapsack 的演算法来做 : : 可是我想了将近一个学期 还是想不出来要怎麽解决 : : 有人可以指导一下吗? : 我不记得我以前是怎麽写的 : 不过我现在有个点子 : 这一题正常的DP要二维table是吧 : 可是他有一个维度最多只有50 : 再考虑你的DP方式,是不是很合适用bitwise operation : (long long 有 64 bits) : 接下来算复杂度=> 5000*100*110 这样要过应该 ok 谢谢你 我看懂了你的方法 (这还是我第一次用bit来存资讯...挺有趣的) 也写出来了 :) 我是将一个数目 将可以凑成这个数目的数字个数 以bit的方式存在表格中 如此便可以将所有情形都列举在一条阵列里面 然後检验全部的情形 便可以求出解 我觉得这一题用bit来存放资讯 同时也压缩了时间复杂度 若不用bitwise operation 铁定会超时的 而且也会浪费很多记忆体空间 是否有更好的方法呢? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.167.12.162