CCC 2007 S5 - Bowling for Numbers

1// CCC 20072// S5: Bowling for Numbers3//4// Algorithm by Konstantin Lopyrev5//6// Although I had thought about dynamic programming7// and moving from one ball to the next, or8// of moving from an array of 1 pin, upwards,9// I never thought of combining them both. This10// was Konstantin's great thought: 2D Dynamic Programming :-)11//12// First you need the sums for the pins13// sum[i] = the sum of the next "width" pins, starting at i14//15// With this array, dynamic programming proceeds16// right to left and top to bottom in a 2D array17// of integers representing the max score for a particular18// combo. That is:19// dp[i][j] is the max score using i balls,20//            with pins j thru number of pins.21//22// With zero balls the max score is zero, so the first row23// is all zero. For the rest the algortithm is;24//      it is the maximum of25//          either the previous result one to the right OR26//          the sum + the maximum score with one less ball,27//                              width places to the right.28//29//30// An example might help: (width = 3 and balls = 3)31// pins =  9  2  8  5  6  7  8  3  2  6  732// sum  = 19 15 19 18 21 18 13 11 15 13  733 34// dp[0]=  0  0  0  0  0  0  0  0  0  0  035// dp[1]= 21 21 21 21 21 18 15 15 15 13  736// dp[2]= 37 37 37 36 36 33 26 18 15 13  737// dp[3]=     * 52 44 39 33 26 18 15 13  738 39// On this last row, dp[3] the right nine positions are just40// from the super sum because we can knock down ALL the pins.41//42// However how do we get the *?43// Answer: If we knocked that pin down we'd take three pins44//         to the right with it (that's 15 from sum) + we'd45//         have the max score from dp[2] three to the right46//         of where we are (that's 36) for a total of 51. But wait47//         we could have 52 if we don't knock down that pin! So48//         * is 52.49// What about the last spot? (the final result)50// Answer: If we knocked that pin down we'd take three pins51//         to the right with it (that's 19 from sum) + we'd52//         have the max score from dp[2] three to the right53//         of where we are (that's 36) for a total of 55. And54//         that's better than the 52 if we didn't knock it down!55//56// This is very fast: all solutions within a second or two.57 58 59import hsa.*;60 61public class CCC2007S5BowlingForNumbersDP62{63    static Console c;64 65    public static void main (String[] args)66    {67	int numberPins, numberBalls, width, s;68	int[] pin;69	int[] sum;70	int[] [] dp;71 72	c = new Console ();73	TextInputFile f = new TextInputFile ("s5.4.in");74 75	int tests = f.readInt ();76	for (int t = 0 ; t < tests ; t++)77	{78 79	    // get input80	    numberPins = f.readInt ();81	    numberBalls = f.readInt ();82	    width = f.readInt ();83	    pin = new int [numberPins];84	    for (int i = 0 ; i < numberPins ; i++)85		pin [i] = f.readInt ();86 87 88	    // load sum:89	    // sum[i] = sum of "width" pins, starting at i90	    sum = new int [numberPins];91	    s = 0;92	    for (int i = 0 ; i < width ; i++)93		s += pin [i];94	    sum [0] = s;95	    for (int i = 1 ; i < numberPins - width + 1 ; i++)96	    {97		s = s - pin [i - 1] + pin [i + width - 1];98		sum [i] = s;99	    }100	    for (int i = numberPins - width + 1 ; i < numberPins ; i++)101	    {102		s = s - pin [i - 1];103		sum [i] = s;104	    }105 106	    // intialize dp107	    dp = new int [numberBalls + 1] [numberPins];108	    for (int j = 1 ; j < numberPins ; j++)109		dp [0] [j] = 0;110	    for (int i = 1 ; i <= numberBalls ; i++)111		for (int j = 1 ; j < numberPins ; j++)112		    dp [i] [j] = -1;113 114	    // fill dp, working right to left and down115	    for (int ball = 1 ; ball <= numberBalls ; ball++)116		for (int i = numberPins - 1 ; i >= 0 ; i--)117		{118		    if (i >= numberPins - width)119			dp [ball] [i] = sum [i];120		    else121			dp [ball] [i] = Math.max (dp [ball - 1] [i + width] + sum [i],122				dp [ball] [i + 1]);123		}124	    c.println (dp [numberBalls] [0]);125	}126    }127}128 129 130 131