Mọi người cho em hỏi bài này bị lỗi ở đâu ạ?
Đề là có n đông sỏi xếp thành 1 hàng , đống thứ i có Ai viên sỏi.Ta có thể ghép hai đống sỏi kề nhau thành một đống và mất 1 chi phí bằng tổng 2 đống sỏi đó.
Yêu cầu: Hãy tìm cách ghép n đôsng sỏi thành 1 đống với chi phí nhỏ nhất.
Vd:
5
4 1 2 7 5
KQ: 41
Code là em đánh nguyên trong phần đáp án ạ
const max=200;
var f:array[1..max,1..max] of longint;
a,s:array[0..max]of longint;
n:longint;
function qhd(i,j:longint):longint;
var k,w:longint;
begin
if f[i,j]<-1 then exit(f[i,j]);
if i=j then
begin
f[i,j]:=0;
exit(0);
end;
f[i,j]:=qhd(i+1,j)+s[j]-s[i-1];
for k:=i+1 to j-1 do begin
w:=qhd(i,k)+qhd(k+1,j-1)+s[j]-s[i-1];
if w<f[i,j] then f[i,j]:=w;
end;
end;
procedure nhap;
var i:longint;
begin
readln
;
for i:=1 to n do read(a);
s[0]:=0;
for i:=1 to n do s:=s[i-1]+a;
end;
begin
nhap;
fillchar(f,sizeof(f),255);
writeln(qhd(1,n));
end.
Đề là có n đông sỏi xếp thành 1 hàng , đống thứ i có Ai viên sỏi.Ta có thể ghép hai đống sỏi kề nhau thành một đống và mất 1 chi phí bằng tổng 2 đống sỏi đó.
Yêu cầu: Hãy tìm cách ghép n đôsng sỏi thành 1 đống với chi phí nhỏ nhất.
Vd:
5
4 1 2 7 5
KQ: 41
Code là em đánh nguyên trong phần đáp án ạ
const max=200;
var f:array[1..max,1..max] of longint;
a,s:array[0..max]of longint;
n:longint;
function qhd(i,j:longint):longint;
var k,w:longint;
begin
if f[i,j]<-1 then exit(f[i,j]);
if i=j then
begin
f[i,j]:=0;
exit(0);
end;
f[i,j]:=qhd(i+1,j)+s[j]-s[i-1];
for k:=i+1 to j-1 do begin
w:=qhd(i,k)+qhd(k+1,j-1)+s[j]-s[i-1];
if w<f[i,j] then f[i,j]:=w;
end;
end;
procedure nhap;
var i:longint;
begin
readln
;for i:=1 to n do read(a);
s[0]:=0;
for i:=1 to n do s:=s[i-1]+a;
end;
begin
nhap;
fillchar(f,sizeof(f),255);
writeln(qhd(1,n));
end.
