/* RIPOFF, ACM MCPC 2009 Problem I, alternate solution by Andy Harrington
Each dataset:
n s t // n number of spaces on the board, 1 to s spaces per turn, max t turns
// followed by n numbers
Input ends with a 0
The score is sum of numbers on spaces where turns end. Find the maximum.
Dynamic program with parameters for the space and the number of turns
to get to it.
*/
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class ripoff
{
static int MAX_N = 200, // check against final problem statement!
CHANGE_BOUND = 9999, n, s, t;
static int[] amt = new int[MAX_N+2]; //numbers on spaces, at start = 0.
public static void main(String[] args) throws Exception {
String file = (args.length > 0) ? args[0] : "ripoff.in";
Scanner in = new Scanner(new File(file));
int[][] best = new int[MAX_N + 2][MAX_N+2];
for (int i = 1; i <= MAX_N+1; i++)
best[0][i] = -MAX_N * CHANGE_BOUND; // impossibly bad
n = in.nextInt();
while (n > 0) {
s = in.nextInt();
t = in.nextInt();
for (int i = 1; i <= n; i++) // at index 0 remains 0
amt[i] = in.nextInt();
amt[n+1] = 0;
if (args.length > 0) judgeCheckData(); // judge integrity check
for (int tt = 1; tt <= t; tt++)
for (int j = tt; j <= n+1; j++)
best[tt][j] = amt[j] +
maxInSeq(best[tt-1], max(tt-1, j - s), j);
int val = best[t][n+1];
for (int tt = 1; tt < t; tt++)
val = max(best[tt][n+1], val);
System.out.println(val);
n = in.nextInt();
}
}
static int maxInSeq(int[] a, int i, int past) { // return max of
int big = a[i]; // a[i].. a[past-1]
for ( ; i < past; i++)
big = max(a[i], big);
return big;
}
// only judge's tests follow:
static void judgeCheckData() {
// check against final problem statement (also bounds at top)!
int MIN_N = 2, MIN_S = 2, MAX_S = 10;
if (n > MAX_N || n < MIN_N || s > MAX_S || s < MIN_S ||
n > s*t || t > n+1) System.err.println("Bad param!");
for (int i = 1; i <= n; i++)
if (abs(amt[i]) > CHANGE_BOUND)
System.err.println("change out of range " + amt[i]);
}
}
|