Skip to content

Instantly share code, notes, and snippets.

@boxysean
Last active December 20, 2015 06:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save boxysean/6084504 to your computer and use it in GitHub Desktop.
Save boxysean/6084504 to your computer and use it in GitHub Desktop.
Class06 - Dynamic Programming
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);
}
}
}
}
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));
}
}
}
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!");
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment