QBMAX spoj – Đường đi có tổng lớn nhất

Nguồn đề bài: http://vn.spoj.com/problems/QBMAX/

1. Đề bài QBMAX spoj

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 a_ij (|a_ij| <= 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

2. Hướng dẫn QBMAX spoj – Đường đi có tổng lớn nhất

Tương tự như bài Đường đi có tổng lớn nhất qua phải hoặc xuống dưới thì ở bài này công thức QHĐ dễ suy ra được

– F[i,j]=max(F[i-1,j-1],F[i,j-1],F[i+1,j-1]) + a[i,j]; với j=2..n, i=1..m.

– Nghiệm bài toán là max(F[i,n]) (với i=1..m)

3. Code tham khảo QBMAX spoj

program QBMAX;
const   fi='';
        nmax=101;
        vc=maxint;
type    matran=array[0..nmax,0..nmax] of integer;

var
        a:matran;
        m,n:byte;
        f:text;

procedure docfile;
var i,j:byte;
begin

        assign(f,fi);
        reset(f);
        readln(f,m,n);

        for i:=0 to m+1 do
                for j:=0 to n+1 do
                        a[i,j]:=-vc;

        for i:=1 to m do
                for j:=1 to n do
                        read(f,a[i,j]);
        close(f);
end;

function max(a,b,c:longint):longint;
begin
        max:=a;
        if max<b then
                max:=b;
        if max<c then
                exit(c);
end;

procedure bpa;
var i,j:byte;
        kq:longint;
begin
        for j:=2 to n do
                for i:=1 to m do
                        a[i,j]:=max(a[i-1,j-1],a[i,j-1],a[i+1,j-1]) + a[i,j];
        kq:=-maxlongint;
        for i:=1 to m do
                if kq<a[i,n] then
                        kq:=a[i,n];
        writeln(kq);
end;

begin
        docfile;
        bpa;
end.