做网站编辑的感受,网站推广多少钱一年,辽宁沈阳又发现一例吗今天,wordpress纯静态化农夫要修理牧场的一段栅栏#xff0c;他测量了栅栏#xff0c;发现需要N块木头#xff0c;每块木头长度为整数Li个长度单位#xff0c;于是他购买了一条很长的、能锯成N块的木头#xff0c;即该木头的长度是Li的总和。 但是农夫自己没有锯子#xff0c;请人锯… 农夫要修理牧场的一段栅栏他测量了栅栏发现需要N块木头每块木头长度为整数Li个长度单位于是他购买了一条很长的、能锯成N块的木头即该木头的长度是Li的总和。 但是农夫自己没有锯子请人锯木的酬金跟这段木头的长度成正比。为简单起见不妨就设酬金等于所锯木头的长度。例如要将长度为20的木头锯成长度为8、7和5的三段第一次锯木头花费20将木头锯成12和8第二次锯木头花费12将长度为12的木头锯成7和5总花费为32。如果第一次将木头锯成15和5则第二次锯木头花费15总花费为35大于32。 请编写程序帮助农夫计算将木头锯成N块的最少花费。 输入格式: 输入首先给出正整数N≤104表示要将木头锯成N块。第二行给出N个正整数≤50表示每段木块的长度。 输出格式: 输出一个整数即将木头锯成N块的最少花费。 输入样例: 8
4 5 1 2 1 3 1 1输出样例: 49 题解在百度百科上了解到了哈夫曼树的定义 结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和通常记作WPL。 若有n个权值为w1,w2,...,wn的结点构成一棵有n个叶子结点的二叉树则树的带权路径最小的二叉树叫做哈夫曼树或最优二叉树。 而这题的模型刚好是哈夫曼树然后我们可以利用优先队列来做这道题 代码 #includecstdio
#includecstring
#includecstring
#includeiostream
#includequeueusing namespace std;int main()
{int n;priority_queueint ,vectorint,greaterint q;cinn;int m,sum0;for(int t0;tn;t){scanf(%d,m);q.push(m);}int x1,x2;while(q.size()1){x1q.top();q.pop();x2q.top();q.pop();sumx1x2;q.push(x1x2);}coutsumendl;return 0;
} 转载于:https://www.cnblogs.com/Staceyacm/p/10782062.html
