描述
在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定在合并过程中最多可以有m(k)次选k 堆石子合并成新的一堆，2≤k≤n，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n 堆石子合并成一堆的最小总费用。
对于给定n堆石子,编程计算合并成一堆的最小总费用。
输入
文件的第1 行有1 个正整数n，表示有n 堆石子。第2行有n个数，分别表示每堆石子的个数。第3行有n-1 个数，分别表示m(k)（2≤k≤n）的值。
输出
程序运行结束时，将计算出的最小总费用输出，问题无解时输出“Nosolution!”
样例输入
7
45 13 12 16 9 5 22
3 3 0 2 1 0
样例输出
136
先找到满足条件的解：
int Search(int amout[],int flag[],int end,int count,int n){
int found = 0;
if(end == count&&amout[end]!=0){
flag[end]++;
return 1;
}
if(end > count||amout[end] == 0){
if(amout[end] == 0)
{
int q;
q=Search(amout,flag,end-1,count,n);
return q;
}
else
{
int r;
r=Search(amout,flag,count,count,n);
return r;
}
}
else if(end < count&&end>=2){
amout[end]--;
flag[end]++;
found = Search(amout,flag,end,count-end+1,n);
amout[end]++;
if(found == 0){
if(flag[end]!=0){
flag[end]--;
int v;
v=Search(amout,flag,end-1,count,n);
return v;
}
flag[end]--;
}
return 1;
}
else{
return 0;
}
}
从后向前查找。例如当n=7时，先查看 一次合并七个的方法是否可以，如果可以合并七个的次数为零，则查找合并6个的次数，如果6个可以合并，那么下一次只需合并两个就满足要求，因此查找n-6+1=2 ,以此类推。
若找到满足条件的解，则从前至后合并序列，以产生最少的中间代价。
for(i=begin;i<=n;i++){
if(flag[i] == 0) continue;
while(flag[i]>0){
temp = 0;
for(j=0;j<i;j++){
H.DeleteMin(x);
temp += x;
}
sum += temp;
H.Insert(temp);
flag[i]--;
}
}
H.Deactivate();
cout<<sum<<endl;
}