H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Từ tập các bài có trên SPOJ (tutorial)
2782. Đường đi có tổng lớn nhất
Mã bài: QBMAX
Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)
Input
Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
Output
Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được
Example
Input:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
Output:
41
Đây là chương trình của mình:
program qbmax;
const fi='qbmax.inp';
fo='qbmax.out';
var f:text;
gtln:longint;
m,n:integer;
b:array [0..101,0..101] of longint;
a:array [0..101,0..101] of integer;
procedure enter;
var i,j:integer;
begin
assign(f,fi);reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function max(x,y,z:longint):longint;
VAR TT:longint;
begin
tt:=x;
if tt<y then tt:=y
else if tt<z then tt:=z;
max:=tt;
end;
procedure optimize;
var i,j:integer;
begin
for j:=0 to n do
begin
b[0,j]:=-maxlongint;
b[m+1,j]:=-maxlongint;
end;
for i:=1 to m do b[i,1]:=a[i,1];
for j:=2 to n do
for i:=1 to m do
b[i,j]:=max(b[i,j-1],b[i+1,j-1],b[i-1,j-1])+a[i,j];
end;
procedure trace;
var i,j:integer;
begin
gtln:=b[1,n];
for i:=2 to m do
if b[i,n]>gtln then gtln:=b[i,n];
end;
procedure printresult;
begin
assign(f,fo);rewrite(f);
writeln(f,gtln);
close(f);
end;
BEGIN
enter;
optimize;
trace;
printresult;
END.
Khi chạy thì mình cho ra kết quả 40 (sai). Vậy mình sai ở chỗ nào? Xin các bạn giúp đỡ cho mình.
2782. Đường đi có tổng lớn nhất
Mã bài: QBMAX
Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)
Input
Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
Output
Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được
Example
Input:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
Output:
41
Đây là chương trình của mình:
program qbmax;
const fi='qbmax.inp';
fo='qbmax.out';
var f:text;
gtln:longint;
m,n:integer;
b:array [0..101,0..101] of longint;
a:array [0..101,0..101] of integer;
procedure enter;
var i,j:integer;
begin
assign(f,fi);reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function max(x,y,z:longint):longint;
VAR TT:longint;
begin
tt:=x;
if tt<y then tt:=y
else if tt<z then tt:=z;
max:=tt;
end;
procedure optimize;
var i,j:integer;
begin
for j:=0 to n do
begin
b[0,j]:=-maxlongint;
b[m+1,j]:=-maxlongint;
end;
for i:=1 to m do b[i,1]:=a[i,1];
for j:=2 to n do
for i:=1 to m do
b[i,j]:=max(b[i,j-1],b[i+1,j-1],b[i-1,j-1])+a[i,j];
end;
procedure trace;
var i,j:integer;
begin
gtln:=b[1,n];
for i:=2 to m do
if b[i,n]>gtln then gtln:=b[i,n];
end;
procedure printresult;
begin
assign(f,fo);rewrite(f);
writeln(f,gtln);
close(f);
end;
BEGIN
enter;
optimize;
trace;
printresult;
END.
Khi chạy thì mình cho ra kết quả 40 (sai). Vậy mình sai ở chỗ nào? Xin các bạn giúp đỡ cho mình.