Hai người thu hoạch trên lưới
Đề 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]$.
Community Discussion