讨论 / 合并果子哪是贪心?明明是动态规划!
春天的蛋 2012-08-04 17:06:00
点我顶贴 收藏 删除
。。。害得我走入歧途。。。
#1 fjxmlhx@2008-03-18 22:14:00
回复 删除
dp。。。你很牛。。。明明是哈夫曼树
#2 muidiay@2008-03-19 16:44:00
回复 删除
大哥我觉得该用二叉树排序。。。。
#3 zhaojianbo@2008-03-19 19:30:00
回复 删除
这个题目解法很多,至少我研究出4种

(1)哈夫曼树

(2)链表

(3)堆

(4)两个队列

前两种效率比后两种低,没急错的话前两种只能的60分(我指NOIP数据,这里是否可以AC就不知道了)

但是这4种解法的核心思想都是贪心,绝对不是动态规划

看来lz对算法理解的有偏差啊,建议你好好看看书。

#4 fjxmlhx@2008-03-19 20:49:00
回复 删除
其实维护两个递增队列就能A的。。
#5 lzsdhr@2008-05-21 16:13:00
回复 删除
王建德老师讲过用堆排做
#6 猥琐晖@2008-05-21 19:06:00
回复 删除
楼上正解
#7 nestman@2008-07-09 09:47:00
回复 删除
我是用快排结合插排做的......

每次把两个重量最小的合并,绝对贪心

经事实证明,这样可以AC......

#8 sunrise@2008-07-09 10:05:00
回复 删除
你牛啊,用DP去吧,

桶排序胜堆排

或二分队列

#9 Inzaghi@2008-07-09 16:57:00
回复 删除
楼主让我无语……

#10 binarie@2008-07-09 17:42:00
回复 删除
汗。。

这题办法多了去了

查看更多回复
提交回复