11079 可以移动的石子合并（必做）
时间限制:1000MS 内存限制:1000K
提交次数:0 通过次数:0
题型: 编程题 语言: C++;C;VC;JAVA
Description
有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，现要将石子合并成一堆，规定每次可选择至少2堆最多k堆移出然后合并，每次合并的分值为新堆的石子数。 若干次合并后，石子最后肯定被合并为一堆，得分为每次合并的分值之和。 现在求解将这n堆石子合并成一堆的最低得分和最高得分。
输入格式
两行。第一行n和k，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100，2<=k<=n。
输出格式
仅一行，为石子合并的最低得分和最高得分，中间空格相连。
输入样例
7 3 45 13 12 16 9 5 22
输出样例
199 593
提示
此题贪心算法求解.
给这题标记标签"dp"方法是同学所为,并非老师标注.动规不是不可以,但有更好更快的贪心解法的.
如7堆石头，每次可选择最少2堆最多3堆合并，可以如下这样合并：
第1次合并：45+22=67
第2次合并：67+16=83
第3次合并：83+13=96
第4次合并：96+12=108
第5次合并：108+9=117
第6次合并：117+5=122
合并的总分值：67+83+96+108+117+122=593，593已是最大分值。
也可以这样合并：
第1次合并：5+9+12=26
第2次合并：13+16+22=51
第3次合并：45+51+26=122
合并的总分值：26+51+122=199，199已是最小分值。
因此此题贪心的方法如下：
（1）保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；
这个和huffman树构造是相同的，不再详述！
（2）保证每次选k堆最少的，合并直至只剩一堆为止，能获得最小得分。
这个是多元huffman树的构造。要注意的是：在合并之前，若n%(k-1)!=1，说明合并到最后一轮时，剩下不是k堆（而是比k堆少），这样算的并不是最小得分，
而必须在合并之前添加若干个为0的虚拟堆，目的为凑成的堆数保证每次都能有k堆合并（包括最后一次）最后合并为1堆。
因此，在合并前作如下处理：
//假设石头每堆个数放于stone[1]~stone[n],且stone[n]之后最多k-1个数组单元为可写;
while (n % (k - 1) != 1)
{
n++;
stone[n]=0;
}
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int stone[100]={0};
int stone1[100]={0};
int k,n;
bool cmp(int a,int b){
return a>b;
}
int findMax(){
for(int i=0;i<n;i++) // 复制新数组
stone1[i]=stone[i];
int res=0;
int sum=stone1[n-1]; // 取最大数
for(int i=n-2;i>=0;i--){
sum+=stone1[i];
res+=sum;
}
return res;
}
int findMin(){
int res=0;
int len=n; // 取长度
while(len%(k-1)!=1) len++; //补齐k的整数个
while(len>=k){ //注意是大于等于
sort(stone,stone+n,cmp); //从大到小排序
int sum =0;//每次都重新计算
for(int j=len-1;j>len-1-k;j--){
sum += stone[j];
}
res+= sum; //累计得分
len = len-k+1; //长度减k-1
stone[len-1] = sum; //合并结果放到队尾
}
return res;
}
int main()
{
freopen("in.txt","r",stdin);
cin >> n >> k;
for(int i=0;i<n;i++)
cin >> stone[i];
sort(stone,stone+n);
cout << findMin()<<" "<<findMax()<<endl;
return 0;
}
扫一扫
3780
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
