-
Notifications
You must be signed in to change notification settings - Fork 0
/
Distinct Coloring
65 lines (55 loc) · 1.85 KB
/
Distinct Coloring
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
//{ Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
// } Driver Code Ends
//User function Template for Java
class Solution{
public static long distinctColoring(int N, int[]r, int[]g, int[]b){
//code here
long [][] dp = new long[3][N];
dp[0][N-1] = r[N-1];
dp[1][N-1] = g[N-1];
dp[2][N-1] = b[N-1];
for(int col=N-2; col>=0; col--){
dp[0][col] = Math.min(dp[1][col+1],dp[2][col+1]) + r[col];
dp[1][col] = Math.min(dp[0][col+1],dp[2][col+1]) + g[col];
dp[2][col] = Math.min(dp[0][col+1],dp[1][col+1]) + b[col];
}
long min = dp[0][0];
for(int i=0; i<3; i++){
min = Math.min(min, dp[i][0]);
}
return min;
}
}
//{ Driver Code Starts.
class GFG
{
public static void main(String args[])throws IOException
{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
int t = Integer.parseInt(read.readLine());
while(t-- > 0)
{
int N = Integer.parseInt(read.readLine());
String input[] = read.readLine().trim().split("\\s+");
int[]r=new int[N];
for(int i=0;i<N;i++)
r[i]=Integer.parseInt(input[i]);
input = read.readLine().trim().split("\\s+");
int[]g=new int[N];
for(int i=0;i<N;i++)
g[i]=Integer.parseInt(input[i]);
input = read.readLine().trim().split("\\s+");
int[]b=new int[N];
for(int i=0;i<N;i++)
b[i]=Integer.parseInt(input[i]);
Solution ob = new Solution();
out.println(ob.distinctColoring(N, r, g, b));
}
out.close();
}
}
// } Driver Code Ends