From
poj 3253
Description
农夫约翰想修复牧场周围的一小部分篱笆。他测量围栏,并发现他需要Ñ(1≤ Ñ ≤20000)厚木板,每一个都具有一些整数长度大号我(1≤ 大号我 ≤50000)单元。然后,他购买了一块足够长的单块长板,足以切入N块木板(即,其长度为长度L i的总和)。FJ忽略了“锯缝”,即锯切时因锯末而损失的额外长度;您也应该忽略它。
FJ遗憾地意识到自己没有切割木头的锯子,于是用长木板将其镶嵌到Farmer Don's Farm上,礼貌地询问他是否可以借用锯子。
壁橱资本家农夫唐(Farmer Don)不借给FJ锯,而是提议就木板中的N -1个切口向农夫约翰收费。切割一块木头的费用恰好等于其长度。切割一块长度为21的木板的成本为21美分。
然后,农夫唐让农夫约翰决定切割木板的顺序和位置。帮助农夫约翰确定他可以用来制作N块木板的最低金额。FJ知道他可以按各种不同的顺序切割木板,这将导致不同的费用,因为最终的中间木板长度不同。
Input
第1行:一个整数N,木板数 第2行至N +1行:每行包含一个整数,描述所需木板的长度
Output
第1行:一个整数:要进行N -1次削减,他必须花费的最低金额
Sample Input
3
8
5
8
Sample Output
34
题目第一眼看上去很难入手,其实是一道奇特的贪心题。
切割的方法可以看成二叉树,每一个叶子节点就对应了切割出的目标木板,叶子节点的深度就对应了得到这块目标所需的切割次数,开销的合计就是每个叶子节点的 木板长度×节点的深度
由此可知,因为木板长度是固定的,所以为了使开销最小,应当使得小长度的木板尽可能节点深,也就是说最短的板与次短的板的节点应当是兄弟节点。这样只需建立优先队列,每次取出最短的2块板合成一块板,直到最后只剩一块板即可。
AC代码:
|
|