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, 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
    ngochahh2005  đã bình luận lúc 8, Tháng 2, 2024, 7:26

    https://ideone.com/nPs0fM


  • 0
    chinhle  đã bình luận lúc 1, Tháng 2, 2024, 15:01

    n,m = list(map(int,input().split()))

    a = [[0]*(150) for _ in range(150)]

    for i in range(1,n+1):

    z = list(map(int,input().split()))
    
    for j in range(1,m+1):
    
        a[i][j] = z[j-1]
    

    f = [[0]*(150) for _ in range(150)]

    for i in range(n):

    f[0][i] = -150**3
    
    f[n+1][i] = -150**3
    

    for j in range(1,m+1):

    for i in range(1,n+1):
    
        f[i][j] = a[i][j]+max(f[i-1][j-1],max(f[i][j-1], f[i+1][j-1]))
    

    ans = -150**3

    for i in range(1,n+1):

    ans = max(ans,f[i][m])
    

    print(ans)


  • -6
    toansoict5232  đã bình luận lúc 17, Tháng 12, 2023, 7:57

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


    • -2
      toansoict5232  đã bình luận lúc 17, Tháng 12, 2023, 7:58

      mấy cái khai báo ở đầu là mình làm cho các bài khác mà quên kh xoá thôi :(