Approach
Each house is painted red, green, or blue, and neighboring houses must have different colors. Because the houses form a circle, the first and last houses are neighbors too, so their colors must differ as well.
Fix the first house’s color and run a linear dynamic program. Let dp[c] be the minimum cost through the current house when that house is painted color c. Initialize all three states to infinity except the fixed first color, whose state is its painting cost. For each later house and color c, the transition is the cost of c plus the smaller previous cost among the other two colors:
next[c] = cost[i][c] + min(dp[(c + 1) % 3], dp[(c + 2) % 3]).
After processing every house, consider only final colors different from the fixed first color. This enforces the circular edge. Repeat for each of the three possible first colors and take the minimum result. Every valid circular coloring has exactly one first color, so these three cases cover all possibilities without accepting an invalid one.
The case N = 2 follows the same rule: the two houses are adjacent around the circle and must have different colors. The final-color check rejects the fixed starting color, leaving precisely those valid choices.
The recurrence uses two rolling arrays of three long values. Costs are stored as input, while the DP state uses constant auxiliary space; the three runs take O(N) time in total. A wide long total and a safely bounded infinity value avoid overflow when costs are accumulated.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static final long INF = Long.MAX_VALUE / 4;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int[][] cost = new int[n][3];
for (int house = 0; house < n; house++) {
for (int color = 0; color < 3; color++) {
cost[house][color] = input.nextInt();
}
}
long answer = INF;
for (int firstColor = 0; firstColor < 3; firstColor++) {
long[] previous = {INF, INF, INF};
long[] current = new long[3];
previous[firstColor] = cost[0][firstColor];
for (int house = 1; house < n; house++) {
for (int color = 0; color < 3; color++) {
current[color] = cost[house][color]
+ Math.min(previous[(color + 1) % 3], previous[(color + 2) % 3]);
}
long[] temp = previous;
previous = current;
current = temp;
}
for (int lastColor = 0; lastColor < 3; lastColor++) {
if (lastColor != firstColor) {
answer = Math.min(answer, previous[lastColor]);
}
}
}
System.out.println(answer);
}
private static class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int pointer;
private int length;
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ');
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
private int read() throws IOException {
if (pointer == length) {
length = in.read(buffer);
pointer = 0;
if (length == -1) {
return -1;
}
}
return buffer[pointer++];
}
}
}