Trò chơi trên ma trận
Xem dạng PDFNgày nay các nhà khoa học đã nghĩ ra 1 trò chơi trên ma trận rất thú vị. Thông qua đó có thể đo IQ một cách khá hiệu quả. Trò chơi được mô tả như sau:
Bạn có ~1~ ma trận ~A~ kích thước ~8 \times N~ trên đó gồm các số nguyên là điểm của các ô đó. Người ta sẽ yêu cầu bạn chọn ~1~ tập khác rỗng các ô trên ma trận này sau đó tính tổng điểm trên những ô này. Trong những ô được chọn không có hai ô nào kề cạnh. IQ của người chơi sẽ tỉ lệ thuận với số điểm nhận được. Sherry tham gia trò chơi và đạt kết quả khá tốt. Bây giờ Sherry muốn biết tổng điểm lớn nhất nhận được trong trò chơi này là bao nhiêu. Bạn hãy giúp Sherry nhé!!!
Input
Dòng đầu tiên là số nguyên ~N~ ~(1 \le N \le 10000)~.
~8~ dòng tiếp theo: Mỗi dòng gồm ~N~ số nguyên. Số nguyên ở hàng ~i~, cột ~j~ là ~A_{ij}~ ~(|A_{ij}| \le 10^{8})~.
Output
Gồm ~1~ dòng duy nhất là số điểm lớn nhất tìm được.
Sample Input
2
-22 2
-33 45
56 -60
-8 -38
79 66
-10 -23
99 46
1 -55
Sample Output
279
Note
Chọn các ô ~(3,1)~ ~(5,1)~ ~(7,1)~ ~(2,2)~.
Bình luận
dp bit mask, mai lam
Bonus: Bài toán tổng quát hơn với giới hạn tổng số ô không vượt quá ~20000~ (số hàng và số cột tự do) cũng có thể giải được trong giới hạn này.
Hint ~1~:
Hint ~2~:
Hint ~3~:
Hint ~4~:
Phân tích độ phức tạp:
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ài này em nghĩ nếu được thì nên thêm test có trường hợp không chọn phần tử cột cuối cùng vẫn đạt được kết quả lớn nhất ạ, code e không xét trường hợp này vẫn AC ạ
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.