QBSELECT - VOI06 Chọn ô
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 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 aij , i =1, 2, 3, 4; j =1, 2, ..., 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 1j , a 2j , a 3j , a 4j , 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.
Example
Input: 3 -1 9 3 -4 5 -6 7 8 9 9 7 2 Output: 32
Hạn chế
Trong tất cả các test: n ≤ 10000, |a ij | ≤ 30000. Có 50% số lượng test với n ≤ 1000.
- Người up: cun
- Nguồn bài: Vietnam Olympiad of Informatics 2006 - Bảng B