Hai người thu hoạch trên lưới

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
75
AC Rate
0.0%
Time limit
2.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 số lượng đá quý $A_{i,j} \ge 0$. Có hai nhà thám hiểm cùng xuất phát từ ô $(1, 1)$ và đi đến ô $(N, M)$. Ở mỗi bước, mỗi người chỉ được đi sang phải hoặc xuống dưới và không đi vào ô -1. Nếu cả hai người cùng đi qua một ô, lượng đá quý ở ô đó chỉ được tính một lần. Hãy tìm tổng lượng đá quý lớn nhất cả hai có thể thu thập, hoặc in ra -1 nếu không có đường đi hợp lệ.

Cấu trúc con tối ưu: xét đồng thời cả hai người sau $k$ bước đi ($r_1 + c_1 = r_2 + c_2 = k$), trạng thái $dp[k][r_1][r_2]$ lưu tổng đá quý lớn nhất khi người 1 ở $(r_1, k-r_1)$ và người 2 ở $(r_2, k-r_2)$.

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

Tổng đá quý lớn nhất thu thập được, hoặc -1 nếu không thể đến $(N, M)$.

Ví dụ
Input Output
3 3
0 1 -1
1 0 -1
1 1 1
5
2 2
1 -1
-1 1
-1
Giới hạn

$1 \le N, M \le 50$, $A_{i,j} \in {-1} \cup [0, 10^6]$.

Draft saved