QBMAX - Đường đi có tổng lớn nhất
Tác giả: ll931110
Ngôn ngữ: Pascal
Program QBMAX;
Const
input = '';
output = '';
Var
A,B: array[0..200,0..200] of longint;
m,n: longint;
Procedure init;
Var
f: text;
i,j: longint;
Begin
Assign(f, input);
Reset(f);
Readln(f, m, n);
For i:= 1 to m do
For j:= 1 to n do read(f, A[i,j]);
Close(f);
End;
Procedure optimize;
Var
f: text;
i,j,s: longint;
Begin
For i:= 0 to n do
Begin
B[0,i]:= -1000000000;
B[m + 1,i]:= -1000000000;
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
Begin
B[i,j]:= B[i - 1,j - 1];
If B[i,j] < B[i,j - 1] then B[i,j]:= B[i,j - 1];
If B[i,j] < B[i + 1,j - 1] then B[i,j]:= B[i + 1,j - 1];
B[i,j]:= B[i,j] + A[i,j];
End;
s:= B[1,n];
For i:= 2 to m do if s < B[i,n] then s:= B[i,n];
Assign(f, output);
Rewrite(f);
Writeln(f, s);
Close(f);
End;
Begin
init;
optimize;
End.