Đường đi có tổng lớn nhất - LCOJ: Luyện Code Online Judge

MAXPATH - Đường đi có tổng lớn nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

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

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

Please read the guidelines before commenting.

-4

tranvandoan1802 đã bình luận lúc 19, Tháng 1, 2026, 9:12 ← sửa 3 →

int main() { int n , m ; cin >> n >> m ; // INPUT; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++){ cin >> a[i][j]; } }

dp[1][1] = a[1][1];

for(int j = 2 ; j <= m ; j++){
    dp[1][j] = dp[1][j-1] + a[1][j] ;
}

for(int i = 2 ; i <= n ; i++) {
    dp[i][1] = dp[i-1][1] + a[i][1];
}

for(int i = 2 ; i <= n ; i++){
    for(int j = 2 ; j <= m ; j++) {
        dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) + a[i][j]; 
    }
}
cout << dp[n][m];

}

0

newbiemuonhochoi đã bình luận lúc 29, Tháng 12, 2024, 8:37

Test case số 4 là gì thế ạ, em bị sai đúng test đó :)))

-6

susu123134 đã bình luận lúc 11, Tháng 11, 2024, 10:09

bài này code python như thế nào vậy ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.