KiloManX.java

KiloManX.java

import java.util.*;

/**
 * SRM 181 Div 1 - 3rd
 */
public class KiloManX {

	public static int leastShots(String[] damageChart, int[] bossHealth) {
		final int size = bossHealth.length;
		final int rows = 1 << size;

		final int[] table = new int[rows];
		final int[][] damage = new int[rows][size];

		for (int i=0; i<rows; ++i) {
			table[i] = Integer.MAX_VALUE;
		}
		table[0] = 0;

		for (int i=0; i<rows; ++i) {
			for (int j=0; j<size; ++j) {
				damage[i][j] = Math.max(1, damage[i][j]);
				if ((i & (1 << j)) != 0) {
					for (int k = 0; k<size; ++k) {
						damage[i][k] = Math.max(damage[i][k], damageChart[j].charAt(k) - '0');
					}
				}
			}
		}

		for (int i=1; i<rows; ++i) {
			for (int j=0; j<size; ++j) {
				int flip = 1 << j;
				if ((i & flip) != 0) {
					int subIdx = i ^ flip;
					int sub = table[subIdx];
					int shot = bossHealth[j] / damage[subIdx][j];
					if (bossHealth[j] % damage[subIdx][j] != 0) shot++;
					table[i] = Math.min(table[i], sub + shot);
				}
			}
		}

		return table[rows-1];
	}

}

state compression DP