a tutorial on computer science

     摘要: 据说不作此题人生不完整。好吧。很久以前就做过了，写过BFS，A*，和双搜。A*用了200+ms,汗，BFS都比他快。正好这几天在看搜索估价函数之类的东西，就把这道经典题拿出来，再做一遍，突然发现，估价函数+迭代加深搜索就是IDA*算法，好吧。以前傻傻看黑书的时候，理解不了A* ，觉得巨麻烦（现在也觉得挺麻烦），现在写起来IDA*，觉得还挺简洁，并且比较通用，而且这玩意又好写又比较通用，就详细研究了一下。看了别人的一个IDA*的算法，觉得写的很简洁很工整，就参详了一下，然后改造成了自己的，A掉了1077题。楼教主写的那个百度之星的版本的Allyes.com，还没有详细看，觉得有点复杂。有机会要好好研究下。  阅读全文

     摘要: 题目链接在这里http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1026
题意很简单：从起始点开始走，最多可以走K步，只能向左，向右，向前走，地图上有一些豆豆，问你最多可以吃到多少豆豆。其实这个题可以这么看，每两个豆豆之间的最短距离是固定的，我们的目的是吃豆豆，不是来玩的，所以就是一个最短哈密顿路径问题，当然题目有一些限制。上篇博客里写的那个用一条链把N个点串起来，求最短长度问题和这个问题是类似的，但是那个题作者给出了一个DP解法，我表示很疑惑。如果看懂了作者的那个办法，这个题就瞬秒了。上一篇在这  阅读全文