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:

DPPATHMAX.jpg

Problem source: Chuyên Sơn La Online Judge


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    godhayuu  đã bình luận lúc 10, Tháng 7, 2025, 13:50
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int a[105][105];
    int dp[105][105];
    
    int main() {
        int m, n;
        cin >> m >> n;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
    
        for (int i = 0; i < m; ++i)
            dp[i][0] = a[i][0];
    
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                dp[i][j] = dp[i][j-1];
                if (i > 0)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
                if (i < m - 1)
                    dp[i][j] = max(dp[i][j], dp[i+1][j-1]);
                dp[i][j] += a[i][j];
            }
        }
    
        int res = dp[0][n-1];
        for (int i = 1; i < m; ++i)
            res = max(res, dp[i][n-1]);
        cout << res << endl;
        return 0;
    }
    

  • 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 đó :)))


  • -1
    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 ạ


    • 0
      Khanh_2004  đã bình luận lúc 8, Tháng 12, 2024, 17:50

      Bài này quy hoạch động trên mảng 2 chiều nhé


      • 0
        Tuan_Kiettt  đã bình luận lúc 20, Tháng 2, 2025, 4:07

        bài này cần gì quy hoạch động đâu =))


        • 0
          Tuan_Kiettt  đã bình luận lúc 20, Tháng 2, 2025, 4:16

          ôi tại mình quên đọc cái chỉ được dịch 3 ô