VOI 06 Bài 1 - Chọn ô
View as 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
Comments
mmb
ban em comment, em xin loi moi nguoi a...
This comment is hidden due to too much negative feedback. Show it anyway.
cẩn thận bị ban nha bạn
tuc tiu qua, thu hoi tin nhan di b
dp bitmask
dp bitmark
This comment is hidden due to too much negative feedback. Show it anyway.
gợi ý:có trường hợp full âm nha
bạn có test khong ạ, mình vãn bị sai 1 test
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.