## Friday, September 16, 2011

### SRM325

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

Dynamic Programming.
RGB stores the cost value for each color of every element, while dp[i][j] stores the cost by using first i elements, with using jth (which is smaller than 3) color for ith (which is smaller than N) element.

### Source Code:

//Fri Sep 16 16:33:59 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class RGBStreet
{
public int[][] RGB;

public int[][] dp;

public int estimateCost(String[] houses)
{
int N = houses.length;
RGB = new int[N][3];
dp = new int[N][3];   //R:0; G:1; B:2;

for(int i=0; i<N; i++){
String[] temp = houses[i].split(" ");
for(int j=0; j<3; j++)
RGB[i][j] = Integer.parseInt(temp[j]);

dp[i][0] = Integer.MAX_VALUE;
dp[i][1] = Integer.MAX_VALUE;
dp[i][2] = Integer.MAX_VALUE;
}

dp[0][0] = RGB[0][0]; dp[0][1] = RGB[0][1]; dp[0][2] = RGB[0][2];

for(int i=1; i<N; i++){
for(int j=0; j<3; j++){
for(int k=0; k<3; k++){
if(j!=k){
dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + RGB[i][j]);
}
}
}
}
return Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2]));
}

}

### Source Code:

//Fri Sep 16 16:43:08 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SalaryCalculator
{
public double calcHours(int P1, int P2, int salary)
{
if(P1 * 200 >= salary) return 1.0 * salary / P1;
return 200.0 + (1.0 * salary - P1 * 200) / P2;
}

}