MAXPATH - Đường đi có tổng lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho một bảng ~A~ kích thước ~m × n~ (~m~ dòng, ~n~ cột), trên đó ghi các số nguyên ~a_{ij}~. 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)~.
Hãy tìm một đường đi sao cho tổng tất cả các số trên đường đi đó là lớn nhất.
Input
- Dòng đầu 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.
Giới hạn:
- ~1 ≤ n, m ≤ 100, |a_{ij}| ≤ 100~
Output
- Gồm một dòng duy nhất ghi tổng lớn nhất tìm được.
Sample
Input #1
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 #1
41
Hint
Giải thích #1:
- Đường đi được mô tả là các ô xanh trong hình dưới đây:
Problem source: Chuyên Sơn La Online Judge
Bình luận
Test case số 4 là gì thế ạ, em bị sai đúng test đó :)))
bài này code python như thế nào vậy ạ
Bài này quy hoạch động trên mảng 2 chiều nhé
bài này cần gì quy hoạch động đâu =))
ôi tại mình quên đọc cái chỉ được dịch 3 ô