作者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