Đường đi có tổng lớn nhất
Xem PDF
Điểm:
900
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một bảng có kích thước \(n\) x \(m\). Mỗi ô trong đó chứa một số nguyên dương. Bạn hãy tìm con đường đi từ ô \((1, 1)\) đến ô \((n, m)\) sao cho tổng các số trên đường đi là lớn nhất. Biết rằng chỉ được đi sang phải hoặc xuống dưới, nghĩa là từ ô \((x, y)\) chỉ có thể đi được đến ô \((x, y + 1)\) hoặc ô \((x + 1, y)\).
Input
- Dòng đầu tiên chứa hai số nguyên dương \(n\), \(m\) \((1 \le n, m \le 1000)\)
- \(n\) dòng tiếp theo, dòng thứ \(i (1 \le i \le n)\) chứa \(m\) số nguyên dương \(a_{i,1}\), \(a_{i,2}\), \(...\), \(a_{i, m}\) \((a_{i, j} \le 10^{10})\)
Output
- In ra tổng lớn nhất có thể đi được.
Example
Test 1
Input
4 4
4 3 2 1
1 2 3 4
4 5 6 7
5 4 3 2Output
29
Bình luận
Bài này mình ra cho vui với lại luyện cho mấy bạn mới và đang học dp OwO
Bài này quay lui là ra Đúng ko anh
=)