Thu thập xu tránh bẫy
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một bảng lưới $N \times M$. Mỗi ô $(i, j)$ có thể là ô cấm -1, hoặc chứa một số nguyên không âm $A_{i,j}$ biểu thị số xu ở ô đó. Bạn xuất phát từ $(1, 1)$ và cần đi đến $(N, M)$, mỗi bước chỉ đi sang phải hoặc xuống dưới và không được đi vào ô -1. Hãy tìm số xu lớn nhất có thể thu thập được, hoặc in ra -1 nếu không thể đến $(N, M)$.
Cấu trúc con tối ưu: $dp[i][j] = A_{i,j} + \max(dp[i-1][j], dp[i][j-1])$ với các ô không bị cấm và có thể đi tới được.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $N, M$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $A_{i,j}$.
Dữ liệu ra
Số xu lớn nhất thu thập được, hoặc -1 nếu không có đường đi.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 2 -1 3 -1 4 1 5 2 |
12 |
| 2 2 1 -1 -1 2 |
-1 |
Giới hạn
$1 \le N, M \le 1000$, $A_{i,j} \in {-1} \cup [0, 10^9]$.
Community Discussion