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 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

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.

 

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

    • Đây là bài QHĐ cơ bản, mình cũng không biết giải thích với bạn ntn nữa,
      Gọi F[i,j] là tổng giá trị lớn nhất của đường đi từ cột 1 đến ô i,j
      như vậy cơ sở QHĐ F[i,1]:=A[i,1] với i=1..m
      Để đến được ô có vị trí [i,j], bạn sẽ có 3 cách đó là đi từ ô [i-1,j-1], [i,j-1] và [i+1,j-1]
      như vậy 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.
      và KQ bài toán sẽ là max(F[i,N]) i=1..m

      • #include
        using namespace std;
        long long n,m,a[101][101],f[101][101],kq=0;
        int main()
        {
        //freopen(“qbmax.inp”,”r”,stdin);
        cin>>m>>n;
        for(int i=1;i<=m;++i)
        for(int j=1;j>a[i][j];
        for(int i=1;i<=m;++i)
        f[i][1]=a[i][1];
        for(int j=1;j<=n;++j)
        for(int i=1;i<=m;++i)
        {
        f[i][j]=max(f[i-1][j-1],max(f[i][j-1],f[i+1][j-1]))+a[i][j];
        kq=max(kq,f[i][j]);
        }
        cout<<kq;
        }
        code c++ ghi vậy đúng k ad

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *