J. DPPAINT – Sơn nhà

Có căn nhà cần sơn. Căn nhà được sơn bằng một trong màu Xanh, Hồng, Vàng với mức giá tương ứng là .

Yêu cầu: Tìm cách sơn màu cho ngôi nhà sao cho hai căn nhà cạnh nhau không được sơn cùng màu và tổng chi phí sơn là ít nhất.

Dữ liệu:

• Dòng đầu chứa số nguyên dương là số ngôi nhà;
• dòng tiếp theo, dòng thứ chứa ba số nguyên dương được ghi cách nhau bởi một dấu cách.

Kết quả:

• Một số nguyên duy nhất là chi phí ít nhất để sơn ngôi nhà.

Ví dụ:

Dữ liệu:

4
13 23 12
77 36 64
44 89 76
31 78 45

Kết quả:

137

Giải thích:

• Các ngôi nhà lần lượt được sơn các màu: Vàng, Hồng, Xanh, Vàng. Tổng chi phí là:

Giới hạn:

• .