Fence Repair

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代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
int n;
ll l[20000+10],ans,l1,l2;
int main()
{
	cin>>n;
	priority_queue<ll,vector<ll>,greater<ll> >que;
	for(int i=0;i<n;i++)
	{
		cin>>l[i];
		que.push(l[i]);
	}
	while(n>1)
	{
		l1=que.top();
		que.pop();
		l2=que.top();
		que.pop();
		que.push(l1+l2);
		ans+=l1+l2;
		n--;
	}
	cout<<ans<<endl;
}