Posted on 2009-03-07 20:05
Lemon 阅读(358)
评论(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过的，看来我的搜索能力还有待提高啊~