Class06 - Dynamic Programming

Main00357LetMeCountTheWaysTopDown.java

package class06;
import java.util.Arrays;
import java.util.Scanner;

// 357 Let Me Count The Ways
// TLE on UVa

public class Main00357LetMeCountTheWaysTopDown {

	public static void main(String[] args) throws Exception {
		new Main00357LetMeCountTheWaysTopDown().run();
	}
	
	int memo[][] = new int[30010][5];
	int coins[] = { 50, 25, 10, 5, 1 };
	
	public int count(int n, int coin) {
		if (n == 0) {
			return 1;
		} else if (coin >= 5 || n < 0) {
			return 0;
		} else if (memo[n][coin] >= 0) {
			return memo[n][coin];
		} else {
			return memo[n][coin] = count(n - coins[coin], coin) + count(n, coin+1);
		}
	}
	
	public void run() throws Exception {
		Scanner in = new Scanner(System.in);
		
		while (in.hasNextInt()) {
			int n = in.nextInt();
			
			for (int[] m : memo) Arrays.fill(m, -1);
			
			int res = count(n, 0);
			
			if (res == 1) {
				System.out.printf("There is only 1 way to produce %d cents change.\n", n);
			} else {
				System.out.printf("There are %d ways to produce %d cents change.\n", res, n);
			}
		}
	}

}

Main10003CuttingSticks.java

package class06;
import java.util.Arrays;
import java.util.Scanner;

// Cutting sticks 10003

public class Main10003CuttingSticks {
	
	public static void main(String[] args) throws Exception {
		new Main10003CuttingSticks().run();
	}
	
	int cuts[] = new int[55];
	int n;
	int memo[][] = new int[55][55];
	
	public int solve(int cutLeft, int cutRight) {
		if (cutLeft+1 == cutRight) {
			return 0;
		} else if (memo[cutLeft][cutRight] >= 0) {
			return memo[cutLeft][cutRight];
		} else {
			int res = 1 << 20;
			int length = cuts[cutRight] - cuts[cutLeft];
			
			for (int i = cutLeft+1; i < cutRight; i++) {
				int cutCost = solve(cutLeft, i) + solve(i, cutRight) + length;
				
				if (cutCost >= 0) {
					res = Math.min(cutCost, res);
				}
			}
			
			return memo[cutLeft][cutRight] = res;
		}
	}
	
	public void run() throws Exception {
		Scanner in = new Scanner(System.in);
		
		while (true) {
			int l = in.nextInt();
			
			if (l == 0) {
				break;
			}
			
			n = in.nextInt();
			
			for (int[] m : memo) {
				Arrays.fill(m, -1);
			}
			
			for (int i = 0; i < n; i++) {
				cuts[i+1] = in.nextInt();
			}
			
			cuts[0] = 0;
			cuts[n+1] = l;
			
//			System.out.println(Arrays.toString(cuts));
			
			System.out.printf("The minimum cutting is %d.\n", solve(0, n+1));
		}
	}
}

Main10945MotherBear.java

package class06;


import java.io.BufferedReader;
import java.io.InputStreamReader;

/* 10945 Mother Bear */

public class Main10945MotherBear {

	public static void main(String[] args) throws Exception {
		new Main10945MotherBear().run();
	}
	
	public void run() throws Exception {
		String line;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		while ((line = in.readLine()) != null) {
			if (line.equals("DONE")) {
				break;
			}
			
			boolean okay = true;
			
			int i = 0;
			int j = line.length()-1;
			
			while (i < j) {
				char a;
				
				do {
					a = line.charAt(i++);
					
					if ('A' <= a && a <= 'Z') {
						a = (char) (a - 'A' + 'a');
					}
				} while (!('a' <= a && a <= 'z'));
				
				char b;
				
				do {
					b = line.charAt(j--);
					
					if ('A' <= b && b <= 'Z') {
						b = (char) (b - 'A' + 'a');
					}
				} while (!('a' <= b && b <= 'z'));
				
				if (a != b) {
					okay = false;
					break;
				}
			}
			
			if (!okay) {
				System.out.println("Uh oh..");
			} else {
				System.out.println("You won't be eaten!");
			}
		}
	}

}