Khai Thác Mỏ Vàng

Dynamic Programming
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một mỏ vàng được biểu diễn bằng lưới $N \times M$, ô $(i, j)$ chứa $a_{i,j}$ lượng vàng. Người thợ mỏ bắt đầu từ bất kỳ ô nào ở cột 1 và đi sang cột $M$. Từ ô $(i, j)$, người thợ có thể di chuyển sang $(i-1, j+1)$, $(i, j+1)$ hoặc $(i+1, j+1)$ (nếu hợp lệ). Hãy tìm lượng vàng tối đa có thể thu hoạch.

Dữ liệu vào
  • Dòng đầu: hai số nguyên dương $N, M$ $(1 \le N, M \le 1000)$.
  • $N$ dòng tiếp theo: mỗi dòng gồm $M$ số nguyên không âm $a_{i,j}$ $(0 \le a_{i,j} \le 10^9)$.
Dữ liệu ra
  • In ra tổng lượng vàng tối đa thu hoạch được.
Ví dụ
Input Output
3 3\n1 3 3\n2 1 4\n0 6 4 12
4 4\n10 33 13 15\n22 21 4 1\n5 0 2 3\n0 6 14 2 83
Giới hạn
  • $1 \le N, M \le 1000$
  • $0 \le a_{i,j} \le 10^9$
  • Thời gian: 1 giây
  • Bộ nhớ: 256 MB
Draft saved