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;
}
相关推荐
有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),现要将石子合并成一堆,规定每次可选择至少2堆最多k堆移出然后合并,每次合并的分值为新堆的石子数。 若干次合并后,石子最后肯定被合并为一堆,得分为每次合并...
可以移动的石子合并
11078 不能移动的石子合并
做如下两个模型的石子合并,如下模型石子都不能移动出列,且合并都仅发生在相邻两堆石子中: (1)第一个模型:一行排列且相邻合并 有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),相邻两堆可合并,合并的...
(1)定义一个n*n的数组A来存储合并石子的最小合并方式,由一开始的只有两堆石子要合并慢慢向上递归得到n堆石子合并的最小得分。 (2)定义另一个于A同秩的矩阵B来存储各个合并中间的剖分 */
Problem D:石子合并(包含源程序c++) Time Limit:1000MS Memory Limit:65536K Description 在一个圆形操场的四周摆放着 n 堆石子. 现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, ...
动态规划 解决石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出...
针对石子合并问题,本文利用动态规划算法寻求石子合并时的最大,最小得分,选择相邻的两堆石子堆进行合并,其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程,利用程序进行求解。算例结果...
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
在一个圆形操场的四周摆放着n 堆石子。...规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题
做如下两个模型的石子合并,如下模型石子都不能移动出列,且合并都仅发生在相邻两堆石子中: (1)第一个模型:一行排列且相邻合并 有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),相邻两堆可合并,合并的...
Problem F:石子合并 Time Limit:1000MS Memory Limit:65536K Total Submit:1180 Accepted:386 Language: not limited Description 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定...
= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20)。 (1)选择一种合并石子的方案,...
不能移动的石子合并的代码
算法分析课程作业,C语言编写,可能需要用input.txt输入,石子合并问题代码
在一个圆形操场上的问题 算法分析经典设计,石子合并课程设计 并外加代码 一套齐全