作业帮石子合并(pascal)
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/24 21:41:50
石子合并(pascal)
【石子合并】
在一个圆形操场的四周摆放着n 堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分.
试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.
【输入文件】
包含两行,第1 行是正整数n（1
【石子合并】
在一个圆形操场的四周摆放着n 堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分.
试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.
【输入文件】
包含两行,第1 行是正整数n（1
这个简单,我以前做过,动态规划,方程为f[i,j]:=min(f[i,j],dp(i,k)+dp(k+1,j)+sum(i,j));
源代码如下：
program shizihebing;
const debug=false;
type integer=longint;
var a,s:array [1..100] of integer;f:array [1..100,1..100] of integer;n:integer;
procedure Init();
var i:integer;
begin
read(n);
for i:=1 to n do
read(a[i]);
filldword(f,n,0);
s[1]:=a[1];
for i:=2 to n do
s[i]:=s[i-1]+a[i];
end;
function min(a,b:integer):integer;
begin
if a<b then min:=a else min:=b;
end;
function sum(i,j:integer):integer;
begin
sum:=s[j]-s[i-1];
end;
function DP(i,j:integer):integer;
var k:integer;
begin
if f[i,j]<>0 then exit(f[i,j]);
//F[i,j]表示把第i到j石子合并所需的最小代价.
if i=j then
begin
exit(0);
end;
if i+1=j then
begin
f[i,j]:=a[i]+a[j];
exit(f[i,j]);
end;
f[i,j]:=high(f[i,j]);//f[i,j]取最大值
for K:=i to j-1 do
begin
f[i,j]:=min(f[i,j],dp(i,k)+dp(k+1,j)+sum(i,j));
end;
exit(f[i,j]);
end;
begin
init();
writeln(dp(1,n));
end.
源代码如下：
program shizihebing;
const debug=false;
type integer=longint;
var a,s:array [1..100] of integer;f:array [1..100,1..100] of integer;n:integer;
procedure Init();
var i:integer;
begin
read(n);
for i:=1 to n do
read(a[i]);
filldword(f,n,0);
s[1]:=a[1];
for i:=2 to n do
s[i]:=s[i-1]+a[i];
end;
function min(a,b:integer):integer;
begin
if a<b then min:=a else min:=b;
end;
function sum(i,j:integer):integer;
begin
sum:=s[j]-s[i-1];
end;
function DP(i,j:integer):integer;
var k:integer;
begin
if f[i,j]<>0 then exit(f[i,j]);
//F[i,j]表示把第i到j石子合并所需的最小代价.
if i=j then
begin
exit(0);
end;
if i+1=j then
begin
f[i,j]:=a[i]+a[j];
exit(f[i,j]);
end;
f[i,j]:=high(f[i,j]);//f[i,j]取最大值
for K:=i to j-1 do
begin
f[i,j]:=min(f[i,j],dp(i,k)+dp(k+1,j)+sum(i,j));
end;
exit(f[i,j]);
end;
begin
init();
writeln(dp(1,n));
end.