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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

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 *