Bài 3. (7 điểm) Quà Tết Trung thu
Để vui Tết Trung thu cho các cháu ban tổ chức thành phố X quyết định phát quà cho mỗi cháu
bằng cách tổ chức một trò chơi trên lưới ô vuông như sau:
Vẽ một hình chữ nhật kích thước M x N ô vuông, Các dòng được đánh số từ 1 đến M, các cột
được đánh số từ 1 đến N (các số được đánh từ trên xuống dưới và từ trái sang phải). mỗi ô nằm
trên giao của dòng i và cột j được gọi là ô (i,j) ghi một số nguyên dương A[i,j], (1 ≤ i ≤ M, 1 ≤
j ≤ N) chính là số món quà trên ô đó. Có thể di chuyển từ một ô sang ô thuộc cột bên phải cùng
dòng hoặc chênh lệch một dòng.
Yêu cầu: Tìm cách giúp các cháu di chuyển từ một ô nào đó của cột bên trái (cột xuất phát)
đến một ô nào đó thuộc cột N (cột đích) sao cho tổng các số của ô đi qua là lớn nhất vì đó
chính là tổng số món quà mà các cháu được nhận.
Dữ liệu: Vào từ file văn bản TIMQUA.INP dòng đầu tiên là 2 số nguyên dương M, N (M, N ≤ 100).
M dòng tiếp theo mỗi dòng N số nguyên A[i,j] (0 ≤ A[i,j] ≤ 50) của hình chữ nhật.
Kết quả: Ghi ra file văn bản TIMQUA.OUT gồm 2 dòng:
- Dòng thứ nhất ghi tổng các số của các ô đi qua.
- Dòng thứ hai ghi N số là chỉ số dòng các ô đi qua từ cột 1 đến cột N.
Ví dụ:
TIMQUA.INP TIMQUA.OUT
50
3 5
7 3 8 1 5
2 3 3 2 1
8 8 3 12 1
6 15 10 5 2
Bạn đang xem bài 3. - Đề chọn HSG tin học Quốc gia năm 2012-2013
