本文共 1363 字，大约阅读时间需要 4 分钟。

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L​i​​个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L​i​​的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

输入首先给出正整数N（≤10​4​​），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成N块的最少花费。

输入样例:

84 5 1 2 1 3 1 1

输出样例:

49

可以采用逆向思维的方法来考虑此问题。

 将最小的两块木板拼在一起，求拼到只剩下一块时的花费为多少。

这是我们可以通过最小堆来实现此问题。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=10005;int n;int a[maxn]; //最小堆int num;   //堆的大小void Create (int x){    int left=x<<1,right=x<<1|1;    int temp=x;    if(left<=num&&a[left]
       
        a[right])    {        temp=right;    }    if(temp!=x)    {        swap(a[temp],a[x]);        Create(temp);    }}void Heap(){    for (int i=num>>1;i>0;i--)        Create (i);}//堆的插入void Insert (int x){     a[++num]=x;     int temp=num;     while (a[temp>>1]>x)     {         a[temp]=a[temp>>1];         temp>>=1;     }     a[temp]=x;}//判断是否为空bool isEmpty(){    return num==0? true:false;}//删除堆int Delete (){    if(isEmpty())        return -1;    int temp=a[1];    int temp2=a[num--];    int child,par;    for (par=1;par<<1<=num;par=child)    {         child=par<<1;         if(child
        
         a[child+1]) child++; if(a[child]
        
       
      
     
    
   

转载地址：http://bpaen.baihongyu.com/