Cho một bảng , ô ở dòng thứ và cột thứ có giá trị là . Ngoài ra còn có miếng domino kích thước để đặt lên bảng. Các miếng domino có thể xoay ngang hoặc dọc, tuy nhiên phải đặt sao cho chúng không đè lên nhau.
Yêu cầu: Hãy tính tổng lớn nhất có thể đạt được của các ô được phủ bởi domino khi đặt toàn bộ miếng domino lên bảng.
Dữ liệu:
Dòng đầu tiên gồm ba số nguyên và ().
dòng tiếp theo, mỗi dòng gồm số nguyên ().
Kết quả: Một số nguyên duy nhất là tổng lớn nhất đạt được.
Ví dụ:
Dữ liệu:
3 5 4
5 6 -9 -3 8
8 4 5 -10 -2
1 0 -10 9 -1
Kết quả:
37
Giải thích:
Cách đặt tối ưu cho ví dụ trên, tổng các ô được chọn là :
