posts - 7, comments - 2, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Copying DNA PKU3633

Posted on 2009-03-07 20:05 Lemon 阅读(348) 评论(0)  编辑 收藏 引用

       一道搜索好题,着实让我费了不少工夫。

       先想到了用位表示每个字母是否已经被用过,一共2^n个不同的状态,根据题目意思就画出了一棵搜索树,根部和叶子结点少,中间很胖,就是C(n,1) + C(n, 2) + … + C(n,n) = 2 ^ n。

       写了一个DP,字符串的比较用两重循环,记忆化,Run了两个测试数据

A

AAAAAAAAAAAAAAAAAA


GTGTACCTGCAGTTGCAG

GGTGGCAAGCTATACAAG


Ans : 6 8

Time: 2000+MS 2000+MS

       又写了一个迭代加深的搜索,Run一下,Time: 1400MS 27000MS,第二测试数据的时间简直无法接受,答案的深度加一,时间就飙了一个数量级。

       又写了BFS广搜,Time: 16MS 500+MS 还是比较满意的,不过还是超时了。我想大概是字符串处理的太慢的,把那段改成用KMP来做,测了下时间更慢了,郁闷~

       最后想到了A*,测了下15MS 170MS,已经挺满意了,不过还是超时,失望啊~我怀疑STL太慢了,于是自己写了一个堆,结果卡过了,PKU 900MS,呵呵~

       这题让我用尽了浑身解数,把这么多算法都回顾了一遍。我知道,有些地方写得不是很好结果超时了,黄队的博客上写用BFS过的,看来我的搜索能力还有待提高啊~


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理