(Đề đề xuất DHBB của THPT CHUYÊN BIÊN HÒA, T. HÀ NAM)
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 vào:
- 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.
Dữ liệu ra:
- Một số nguyên duy nhất là chi phí ít nhất để sơn ngôi nhà.
Ví dụ:
Dữ liệu vào:
4
13 23 12
77 36 64
44 89 76
31 78 45
Dữ liệu ra:
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:
- .
