VOI 06 Bài 1 - Chọn ô
Xem dạng PDFCho một bảng hình chữ nhật kích thước ~4×n~ ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.
Ô nằm trên giao của dòng i và cột j được gọi là ô ~(i,j)~. Trên mỗi ô ~(i,j)~ có ghi một số nguyên ~a_{i,j}~, ~i = 1, 2, 3, 4;~ ~j = 1, 2, \dots, n~. Một cách chọn ô là việc xác định một tập con khác rỗng ~S~ của tập tất cả các ô của bảng sao cho không có hai ô nào trong ~S~ có chung cạnh. Các ô trong tập ~S~ được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. Tìm cách chọn sao cho trọng lượng là lớn nhất.
Ví dụ: Xét bảng với ~n = 3~ trong hình vẽ dưới đây:
Cách chọn cần tìm là tập các ô ~S = \{(3,1), (1,2), (4,2), (3,3)\}~ với trọng lượng 32.
Input
Dòng đầu tiên chứa số nguyên dương n là số cột của bảng.
Cột thứ j trong số n cột tiếp theo chứa 4 số nguyên ~a_{1,j}~ , ~a_{2j,}~ , ~a_{3,j}~ , ~a_{4,j}~, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng.
Output
Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.
Giới hạn
Trong tất cả các test: ~n \leq 10\,000~, ~|a_{i,j}| \leq 30\,000~.
Có 50% số lượng test với ~n \leq 1000~.
Sample Input
3
-1 9 3
-4 5 -6
7 8 9
9 7 2
Sample Output
32
Bình luận
ban em comment, em xin loi moi nguoi a...
một diễn đàn học tập lớn như vậy mà bạn có phát ngôn một cách thô thiển vậy sao ?!?!
cẩn thận bị ban nha bạn
tuc tiu qua, thu hoi tin nhan di b
dp bitmask
dp bitmark
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
gợi ý:có trường hợp full âm nha
bạn có test khong ạ, mình vãn bị sai 1 test
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.