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ừ ô ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | 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. |
