TopCoder SRM 468 DIV 2 250

RoadOrFlight.java

/**
 * @author Taketo Yoshida
 */
public class RoadOrFlight {
  private Solver solver;

  enum SolverType { DP, FULL_SEARCH, MEMODFS }
  class SolverNotFoundException extends Exception {
    public SolverNotFoundException(String msg) { super(msg); }
  }

  interface Solver {
    public int solve(int N, int[] roadTime, int[] flightTime, int K);
  }

  /*
   * Full Searching
   */
  class FullSearhingSolver implements Solver {
    public int solve(int N, int[] roadTime, int[] flightTime, int K) {
      int sum, min = Integer.MAX_VALUE;
      for (int i = 0; i < (1 << N); i++) {
        if(bitCount(i) > K) continue;
        sum = 0;
        for (int j = 0; j < N; j++) {
          sum += ((i & (1 << j)) != 0) ? flightTime[j] : roadTime[j];
        }
        if (min > sum) min = sum;
      }
      return min;
    }
    int bitCount(int val) {
      int ret = 0;
      for (int i=0 ; i < 32; i++) {
        if((val & (1 << i)) != 0) ret++;
      }
      return ret;
    }
  }

  /*
   * Memorized DFS
   */
  class MemoDfsSolver implements Solver {
    private int roadTime[];
    private int flightTime[];
    private int memo[][];
    private final int NOT_MEMORIZED = -1;
    public MemoDfsSolver() {}
    public int solve(int N, int[] roadTime, int[] flightTime, int K) {
      this.roadTime = roadTime;
      this.flightTime = flightTime;
      memo = new int[N+1][K+1];
      for (int i = 0; i <= N; i++) for (int j = 0; j <= K; j++) memo[i][j] = NOT_MEMORIZED;
      int ret = time(N, K);
      return ret;
    }
    public int time(int i, int j) {
      if (i == 0) return 0;
      if (memo[i][j] != NOT_MEMORIZED) return memo[i][j];
      if (j <= 0) 
        memo[i][j] = time(i-1, j) + roadTime[i-1];
      else 
        memo[i][j] = Math.min(time(i-1, j) + roadTime[i-1], time(i-1, j -1) + flightTime[i-1]);
      return memo[i][j];
    }
  }

  /*
   * Dynamic Programming
   */
  class DpSolver implements Solver {
    public int solve(int N, int[] roadTime, int[] flightTime, int K) {
      int dp[][] = new int[N + 1][K + 1];
      for (int j = 0; j <= K; j++) dp[0][j] = 0;
      for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
          dp[i][j] = (j > 0) ? 
            Math.min(dp[i - 1][j] + roadTime[i - 1], dp[i - 1][j - 1] + flightTime[i - 1]) :
            dp[i - 1][j] + roadTime[i - 1];
        }
      }
      return dp[N][K];
    }
  }

  public RoadOrFlight(SolverType type) throws SolverNotFoundException {
    if (type == SolverType.DP) {
      solver = new DpSolver();
    } else if (type == SolverType.FULL_SEARCH) {
      solver = new FullSearhingSolver();
    } else if (type == SolverType.MEMODFS) {
      solver = new MemoDfsSolver();
    } else {
      throw new SolverNotFoundException("this type is not found.");
    }
  }

  public static void main(String[] args) {
    try { (new RoadOrFlight(SolverType.DP)).runTest(-1); } catch(SolverNotFoundException e) {}
  }

  public void runTest(int testCase) {
    if ((testCase == -1) || (testCase == 0)) testCase0();
    if ((testCase == -1) || (testCase == 1)) testCase1();
    if ((testCase == -1) || (testCase == 2)) testCase2();
  }

  private void verifyCase(int testCase, long expected, long received) {
    System.err.println("Test Case #" + testCase + "...");
    if (expected == received) {
      System.err.println("PASSED"); 
    } else { 
      System.err.println("FAILED"); 
      System.err.println("\tExpected: \"" + expected + '\"');
      System.err.println("\tReceived: \"" + received + '\"');
    }
  }

  private void testCase0() {
    int Arg0 = 3; int Arr1[] = {1, 2, 6}; int Arr2[] = {4, 3, 5}; int Arg3 = 2; 
    verifyCase(0, 8, solver.solve(Arg0, Arr1, Arr2, Arg3));
  }

  private void testCase1() {
    int Arg0 = 3; int Arr1[] = {4, 6, 7}; int Arr2[] = {3, 2, 3}; int Arg3 = 2; 
    verifyCase(1, 9, solver.solve(Arg0, Arr1, Arr2, Arg3));
  }

  private void testCase2() {
    int Arg0 = 10; int Arr1[] = {4, 6, 7, 8, 7, 4, 9, 4, 10, 5}; int Arr2[] = {3, 2, 3, 4, 2, 4, 5, 4, 6, 2}; int Arg3 = 5; 
    verifyCase(2, 43, solver.solve(Arg0, Arr1, Arr2, Arg3));
  }
}