算法题整理——堆
POJ1456_Supermarket描述超市里的商品有两个属性，过期时间和利润值，现在规定过期商品只能丢掉，而且超市每天只能卖一件商品，求获利最大值。
数据范围商品数目，过期时间和利润均为1e4之内的正整数。
思路不妨先假设没有两件商品在同一天过期。
显然到最后一件商品过期的那天，超市只剩下了这一
...
算法题整理——KMP
发表于
|
分类于
基础算法
在做字符串的匹配时，我们有字符串S和T，现在想要从S中找到等于T的连续子串，一个朴素的想法是从S的每个字符开始，逐个和T的字符匹配，如果匹配不成功，再从S的下一个字符开始逐个匹配，这样的算法复杂度是O(NM)。
为了优化算法，我们注意到一个事实，即当我们匹配失败时，前面一定有一部分字符是匹配成功了的
...
算法题整理——Huffman树和字典树
发表于
|
分类于
基础算法
Huffman树CH1701_合并果子描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并
...
算法题整理——Hash
发表于
|
分类于
基础算法
POJ3349_Snowflake Snow Snowflakes描述有n片雪花，每个雪花使用6个整数来描述其每个角。比如1，2，3，4，5，6，描述可以从任意一个角开始，比如上面的雪花也可以被描述为2，3，4，5，6，1，也可以是逆序的如3，2，1，6，5，4只要按一个圈来描述六个角就行。
现在，
...
算法题整理——差分和前缀和
发表于
|
分类于
基础算法
差分POJ3263_Tallest Cow描述Farmer John 有N头牛排列成一排，当两头牛i，j之间的牛身高都小于它们时，这两头牛可以看到对方。
现在，知道最高的牛的编号是I，身高为H，以及R对可以相互看到对方的牛的编号。
在让每头牛都尽可能高的情况下，求出所有牛的身高。
数据范围1 ≤ N
...
算法题整理——A*和IDA*搜索
发表于
|
分类于
基础算法
A*POJ1077_Eight
据说这道题是不做人生就不完整的典中典
看到这个9Puzzle，我突然想起了隔壁MasterMa努力两周不眠不休的16Puzzle
幸好我没选上人工智能……
描述求解八数码问题，并用“lrud”来描述空格子移动的方向，输出移动次数最少的
...