Lưới Chiến Thuật
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một bảng lưới kích thước R x C, mỗi ô (i, j) có giá trị nguyên không âm a_{i,j}. Bạn cần chọn một tập các ô sao cho không có hai ô nào được chọn chung cạnh với nhau, đồng thời tổng giá trị các ô được chọn là lớn nhất có thể.
Dữ liệu vào
- Dòng đầu: hai số nguyên R và C (1 ≤ R, C, R × C ≤ 484).
- R dòng tiếp theo, mỗi dòng chứa C số nguyên a_{i,j} (0 ≤ a_{i,j} ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: tổng giá trị lớn nhất có thể chọn.
Ví dụ
| Input | Output |
|---|---|
| 2 2\n1 2\n3 4 | 5 |
Giới hạn
- R × C ≤ 484
- 0 ≤ a_{i,j} ≤ 10^9
Community Discussion