Sơn Nhà Ba Màu

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved