第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
石子合并--在一个圆形操场的四周摆放着n 堆石子.doc
石子合并
一．
试题
在一个园形操场的四周摆放 N 堆石子（N≤100），现要将石子有次序地合并成
一堆。规定
每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的
得分。
编一程序，由文件读入堆数 N 及每堆的石子数（n≤２０），
①选择一种合并石子的方案，使得做 N－1 次合并，得分的总和最小；
②选择一种合并石子的方案，使得做 N－1 次合并，得分的总和最大。
例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依
次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３
得分最大的方案为：１４＋１８＋２２＝５４
输入数据：
文件名由键盘输入，该文件内容为：
第一行为石子堆数 N；
第二行为每堆的石子数，每两个数之间用一个空格符分隔。
输出数据：
输出文件名为 output.txt
从第 1 至第 N 行为得分最小的合并方案。第 N＋1 行是空行。从第 N＋2 行到
第 2N＋1 行是得分最大合并方案。
每种合并方案用 N 行表示，其中第 i 行（1≤i≤N）表示第 i 次合并前各堆的石
子数（依顺时针次序输出，哪一堆先输出均可）。 要求将待合并的两堆石子数以相应的负
数表示，以便标识。
最后两行分别为最小合并得分和最大合并得分。
输入输出范例：
输入文件内容：
４
４ ５９ ４
输出文件内容：
－４ ５ ９ －４
－８－５ ９
－１３ －９
２２
４ －５ －９ ４
４ －１４ －４
－４－１８
２２
43
54
program gpopo;
a:array[1..400]of integer;
q:array[0..400]of integer;
f:array[1..200,1..200]of integer;
begin
assign(input,'stone.in');
assign(output,'stone.out');
reset(input);
rewrite(output);
read(n);
for i:=1 to n do
read(a[i]);
a[i+n]:=a[i];
end;
fillchar(f,sizeof(f),0);
q[1]:=a[1];
q[0]:=0;
for i:=2 to 2*n do
q[i]:=q[i-1]+a[i];
for j:=2 to n do
for i:=1 to 2*n-j+1 do
begin
min:=0;
for k:=1 to j-1 do
min:=f[i,k]+f[i+k,j-k]+q[i+j-1]-q[i-1];
if f[i,k]+f[i+k,j-k]+q[i+j-1]-q[i-1]>min then
f[i,j]:=min;
end;
min:=f[1,n];
for i:=2 to n do
if f[i,n]>min then min:=f[i,n];
writeln(min);
close(input);
close(output);
end.
【石子合并】
在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次
只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将 n 堆石子合并成一堆的最小得分和最大得分。
【输入文件】
包含两行，第 1 行是正整数 n（1<=n<=100），表示有 n 堆石子。
第 2 行有 n 个数，分别表示每堆石子的个数。
【输出文件】
输出两行。
第 1 行中的数是最小得分；第 2 行中的数是最大得分。
【输入样例】
4
4 4 5 9
【输出样例】
43
54
【分析】
本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个
条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子：
6
3 4 6 5 4 2
如果使用贪心法求最小得分，应该是如下的合并步骤：
第一次合并 3 4 6 5 4 2
2,3 合并得分是５
第二次合并 5 4 6 5 4
5,4 合并得分是 9
第三次合并 9 6 5 4
5,4 合并得分是 9
第四次合并 9 6 9
9,6 合并得分是 15
第五次合并 15 9
15,9 合并得分是 24
总得分＝5＋9＋9＋15＋24＝62
但是如果采用如下合并方法，却可以得到比上面得分更少的方法：
第一次合并 3 4 6 5 4 2
3,4 合并得分是 7
第二次合并 7 6 5 4 2
7,6 合并得分是 13
第三次合并 13 5 4 2
4,2 合并得分是 6
第四次合并 13 5 6
5,6 合并得分是 11
第五次合并 13 11
13,11 合并得分是 24
总得分＝7＋13＋6＋11＋24＝61
由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为 13
和 11 的相邻两堆。 这两堆石头分别由最初 的第 1，2，3 堆（石头数分别为 3，4，6）和
第 4，5，6 堆（石头数分别为 5，4，2）经 4 次合并后形成的。于是问题又归结为如何使得
这两个子序列的 N－2 次合并的得分总和最优。为了实现这一目标，我们将第１个序列又一
分为二：第１、２堆构成子序列１，第３堆为子序列２。第一次合并子序列１中的两堆，得
分７；第二次再将之与子序列２的一堆合并，得分 13。显然对于第１个子序列来说，这样
的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列１，第５，
６堆构成子序列２。第三次合 并子序列２中的２堆，得分６；第四次再将之与子序列１中
的一堆合并，得分 13。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得
出一个结论──６堆石子经过这样的５次合并后，得分的总和最小。
动态规划思路：
阶段 i：石子的每一次合并过程，先两两合并，再三三合并，...最后 N 堆合并
状态 s：每一阶段中各个不同合并方法的石子合并总得分。
决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方
案
具体来说我们应该定义一个数组 s[i,j]用来表示合并方法，i 表示从编号为 i 的石头开
始合并，j 表示从 i 开始数 j 堆进行合并，s[i,j]为合并的最优得分。
对于上面的例子来说，初始阶段就是 s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开
始还没有合并，所以这些值应该全部为 0。
第二阶段：两两合并过程如下，其中 sum(i,j)表示从 i 开始数 j 个数的和
s[1,2]=s[1,1]+s[2,1]+sum(1,2)
s[2,2]=s[2,1]+s[3,1]+sum(2,2)
s[3,2]=s[3,1]+s[4,1]+sum(3,2)
s[4,2]=s[4,1]+s[5,1]+sum(4,2)
s[5,2]=s[5,1]+s[6,1]+sum(5,2)
s[6,2]=s[6,1]+s[1,1]+sum(6,2)
第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个
为一组
s[1,3]=s[1,2]+s[3,1]+sum(1,3)或 s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最优
s[2,3]=s[2,2]+s[4,1]+sum(2,3)或 s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最优
.
.
第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。
以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可。
由此得到算法框架如下：
For j←2 to n do
{枚举阶段，从两两合并开始计算}
For i←1 to n do
{计算当前阶段的 n 种不同状态的值}
For k←1 to j-1 do {枚举不同的分段方法}
Begin
If i+k>n then t←(i+k) mod n else t←i+k {最后一个连第一个的情况处理}
s[i,j]←最优{s[i,k]+s[t,j-k]+sum[1,3]} {sum[i,j]表示从 i 开始数 j 个数的和}
end;
var
n:integer;
a:array[1..100] of longint;
s:array[1..100,1..100] of longint;
t:array[0..100,0..100] of longint;
i,j,k,temp,max,min:longint;
begin
assign(input,'shizi.in');
reset(input);
readln(n);
fillchar(t,sizeof(t),0);
{计算和数组}
for i:=1 to n do
read(a[i]);
for i:=1 to n do
for j:=1 to n do
for k:=i to i+j-1 do
begin
if k>n then temp:=k mod n else temp:=k;
t[i,j]:=t[i,j]+a[temp];
end;
{动态规划求最大得分}
fillchar(s,sizeof(s),0);
for j:=2 to n do
for i:=1 to n do
for k:=1 to j-1 do
begin
if i+k>n then temp:=(i+k) mod n else temp:=i+k;
{处理环形问题}
max:=s[i,k]+s[temp,j-k]+t[i,j];
if s[i,j]n then temp:=(i+k) mod n else temp:=i+k;
{处理环形问题}
s[i,j]:=s[i,k]+s[temp,j-k]+t[i,j];
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
