Thu thập xu tránh bẫy

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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]$.

Draft saved