Sơn Nhà Ba Màu
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ ngôi nhà xếp thành một hàng. Mỗi ngôi nhà cần được sơn bằng một trong 3 màu: Đỏ, Xanh lá hoặc Xanh dương. Chi phí sơn ngôi nhà thứ $i$ bằng 3 màu này lần lượt là $r_i, g_i, b_i$.
Hãy tìm tổng chi phí nhỏ nhất để sơn hết $N$ ngôi nhà sao cho không có hai ngôi nhà kề nhau nào có cùng màu.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên không âm $r_i, g_i, b_i$ ($0 \le r_i, g_i, b_i \le 10^9$).
Dữ liệu ra
- In ra tổng chi phí sơn nhà nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3\n17 2 17\n16 16 5\n14 3 19 | 10 |
| 1\n7 6 2 | 2 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le r_i, g_i, b_i \le 10^9$
Community Discussion