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.

Download