Commits

littledot5566  committed b31fd4b

srm563 lvl3 SpellCardsEasy, incomplete.

  • Participants
  • Parent commits 9751941

Comments (0)

Files changed (2)

File src/srm563/SpellCardsEasy.java

 package srm563;
 
 public class SpellCardsEasy {
+	public int maxDamage(int[] level, int[] damage) {
+		return new DynamicProgramming().maxDamage(level, damage);
+	}
+
+}
+
+class DynamicProgramming {
+	int[]	level, damage;
+	int		DMG	= 0;
+
+	public int maxDamage(int[] level, int[] damage) {
+		this.level = level;
+		this.damage = damage;
+
+		int maxDMG = 0;
+		for (int dmg : damage)
+			maxDMG += dmg;
+
+		boolean playable = play(0, 0, 0, maxDMG);
+		if (playable)
+			skip(0, 0, 0, maxDMG);
+
+		return DMG;
+	}
+
+	private boolean play(int pos, int req, int dmg, int max) {
+		boolean played = true;
+		if (level.length - pos - req >= level[pos]) {
+			req += level[pos] - 1;
+			dmg += damage[pos];
+
+			if (dmg > DMG)
+				DMG = dmg;
+		} else {
+			played = false;
+			if (req > 0)
+				req--;
+		}
+
+		int maxDMG = max - damage[pos];
+
+		if (pos + 1 < level.length && maxDMG > DMG - dmg) {
+			boolean playable = play(pos + 1, req, dmg, maxDMG);
+			if (playable)
+				skip(pos + 1, req, dmg, maxDMG);
+		}
+
+		return played;
+	}
+
+	private void skip(int pos, int req, int dmg, int max) {
+		int maxDMG = max - damage[pos];
+
+		if (maxDMG > DMG - dmg) {
+			if (req > 0)
+				req--;
+			if (pos + 1 < level.length) {
+				play(pos + 1, req, dmg, maxDMG);
+				skip(pos + 1, req, dmg, maxDMG);
+			}
+		}
+	}
+}
+
+class Recursive {
 	private int	DMG	= 0;
 	private int[]	L, D;
 	private int		N;
 			}
 		}
 
-//		System.err.format("p=%d d=%d H=", pos, dmg);
-//		for (int i = 0; i < N; i++)
-//			System.err.print(H[i] + " ");
-//		System.err.println();
-
 		// play next card
 		if (pos + 1 < N)
 			for (int i = 0; i < N; i++)

File src/srm563/SpellCardsEasyTest.java

 		p2 = 7268;
 		all_right = KawigiEdit_RunTest(7, p0, p1, true, p2) && all_right;
 
-		p0 = new int[] { 34, 32, 19, 8, 34, 6, 23, 18, 35, 33, 17, 8, 17, 19, 38,
-				38, 30, 3, 35, 10, 2, 20, 34, 32, 34, 3, 1, 13, 37, 30, 31, 2, 21, 31,
-				1, 22 };
-		p1 = new int[] { 681, 524, 395, 321, 541, 384, 532, 565, 665, 529, 561,
-				545, 560, 493, 415, 617, 496, 684, 325, 460, 512, 389, 684, 677, 648,
-				320, 459, 576, 450, 596, 413, 572, 446, 416, 548, 631 };
-		all_right = KawigiEdit_RunTest(7, p0, p1, false, p2) && all_right;
+		p0 = new int[] { 3, 5, 1, 1, 3, 6, 1, 3, 6, 7, 1, 6, 1, 5, 7, 5, 7, 1, 7,
+				4, 4, 4, 1, 7, 5, 7, 2, 4, 3, 2, 7, 1, 7, 2, 6, 5, 4, 7, 2 };
+		p1 = new int[] { 243, 250, 262, 288, 271, 260, 283, 269, 292, 245, 275,
+				252, 251, 282, 234, 240, 284, 267, 287, 235, 272, 259, 253, 258, 249,
+				279, 275, 266, 275, 292, 229, 242, 270, 254, 274, 275, 290, 263, 249 };
+		p2 = 4813;
+		all_right = KawigiEdit_RunTest(8, p0, p1, true, p2) && all_right;
 
 		if (all_right) {
 			System.out.println("You're a stud (at least on the example cases)!");