Kinh nghiệm (OLP 10&11 - 2019)
Xem PDFHai anh em An và Bình tham gia một trò chơi thám hiểm trên bảng số \(xTremeMaze\).
Bảng có kích thước \(N\)x\(M\) (\(N\) dòng và \(M\) cột). Các ô trong bảng được đánh số từ trái sang phải và từ
trên xuống dưới.
Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi
đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người
chơi sẽ bị giảm nếu đi vào ô này.
An và Bình bắt đầu tại ô trái trên, đánh số là (\(1, 1\)). Mỗi lượt, một người chỉ có thể di chuyển tới ô
kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi
qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết
thúc tại ô (\(N, M\)).
Mục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô
mà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí (\(1, 1\)) và ô kết thúc
tại vị trí (\(N, M\)). Quy ước: giá trị điểm kinh nghiệm tại ô (\(1, 1\)) và ô (\(N, M\)) đều bằng 0.
Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt
được.
Input
- Dòng đầu chứa hai số nguyên \(N\) và M (\(2 \le N, M \le 200\)), số dòng và số cột của bảng.
- \(N\) dòng tiếp theo, mỗi dòng ghi M số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng.
Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.
Output
- Ghi ra duy nhất một số nguyên là tổng điểm lớn nhất mà
An cùng với Bình đạt được.
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N \le 3\) và \(M \le 200\).
- Subtask \(2\) (\(40\%\) số điểm): \(N \le 50\) và \(M \le 50\).
- Subtask \(3\) (\(30\%\) số điểm): Không có điều kiện gì thêm.
Example
Test 1
Input
3 3
0 2 3
4 5 6
7 8 0Output
32
Bình luận
Hint:
Gọi (x, y) là vị trí hiện tại của bạn An
Gọi (x', y') là vị trí hiện tại của bạn Bình
Ban đầu (x, y) = (x', y') = (1, 1)
Xét 4 trường hợp di chuyển: {\(\downarrow, \downarrow\)}, {\(\downarrow, \rightarrow\)}, {\(\rightarrow, \downarrow\)}, {\(\rightarrow, \rightarrow\)}
Khi đi qua ô nào đó, ta tăng giá trị tại vị trí của 2 bạn
Khi di chuyển ra ngoài biên phải \(m\) (\(\rightarrow\)) hoặc xuống qua biên dưới \(n\) (\(\downarrow\)) hoặc 2 thằng gặp nhau tại vị trí khác (1, 1) và (n, m) ta return -oo để loại bỏ tổng tính được vì nó không tham gia kết quả
Độ phức tạp \(O(n^2 * m^2)\)
Nhận xét: \(x + y = x' + y'\) nên khi biết 3 giá trị thì số còn lại cũng có thể tính được, nên thực tế chỉ cần \(O(n^2 * m)\)
Advance:
Giải với \(n * m \leq 40000\)
Giải với vị trí xuất phát khác nhau nhưng cùng điểm đến
Giải với vị trí xuất phát giống nhau nhưng khác điểm đến
Giải với k vị trí xuất phát đến k điểm đến tương ứng
2 bình luận nữa