hdoj1789

思路:先按分值从大到小排序,然后从前往后一一考虑每个任务能否完成,若可以完成,则完成那天越靠后越好,这样可以为其它任务留下最大的余地。
标注:这题还有一些不明白的地方,回头须细细复习琢磨。。

hdoj1045——fire net

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1045
贪心题,原先想的太简单,以为从左上角开始依序放置就行了,结果sample都过不了。。后来想到了贪心的一种方法:既然要使放置的越多越好,那么应当尽量先占据对附近影响最小的格子,这样就为后续放碉堡提供了好的条件。
如何衡量一个格子对附近格子的影响大小呢?可以这样做:用这个格子一旦放置碉堡,将会使多少格子无法再放碉堡来衡量。具体实现方面,可以设置一个w[][]数组,每个元素代表该格若放置碉堡将影响的格子的数量。然后将w[][]数组的内容放入结构体数组b[]的v。按v升序排序b数组。从1开始按b数组的顺序试探可否放置碉堡即可。
(上述贪心算法正确性证明我还没想到,但能保证AC,不排除算法错,而数据较宽松的情况。。)

hdoj1053——huffman编码

这道题的题意很清楚,就是构造huffman编码,但是以前没写过huffman树,一时不知道怎么写,为了这个知识点,特意去图书馆找书(当然数据结构书上是有详细叙述的,但那不是我要的答案,因为我想找到一种更适合在acm比赛中表达的方法),找了N多书终于在一本《离散数学及算法》的书上找到了huffman树的一种数组表示,也没怎么看,因为用了很多数组,比较繁琐。。只是让我找到了一种思路,用数组构造huffman树.
想了很久(主要是太笨了。。~),终于想到了构造的方法。首先读入字符串,用a数组统计各个字母数字以及下划线的出现频率,然后将这些信息写入结构体数组p。p数组每个元素代表一个节点。所以写入完成后,p[i]保存了一个字母(或数字、下划线)的出现次数。这样,p数组各个元素就是huffman树的叶子节点,它的值是出现次数。接下来循环count-1次构造huffman树,每次把生成的父节点往后加进去(详见下面代码,为什么这么构造,这段代码啥意思?–!请把《数据结构》再翻个几遍。。)。注意每次排序的范围,每次去掉2个元素,生成一个元素(j=j+2)。
接下来就好办了,因为huffman树已经生成好了,该给每个节点加上深度值了。方法是从根开始bfs这棵树,依次加上深度值就行了(叶子节点的深度值就是一个字母(或数字、下划线)的编码长度)。最后遍历queue,如果是叶子节点就计算编码后长度即可。
到此,这道题目还未完成,提交果断WA。原因在于只出现一种字符的情况(可以按程序流程走下去,看这种情况下输出会如何),单独考虑即可(==!作为菜鸟,不幸地WA两次。。)。
哈哈,虽然花了很多时间,不过学到了新的知识,还是非常值得的~~。