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

 

2 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

Trả lời

Thư điện tử 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 *