LightOJ 1017 - Brush (III) http://lightoj.com/volume_showproblem.php?problem=1017 DP

LightOJ1017.java

import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1017 {

        public void run() {
		Scanner cin = new Scanner(System.in);
		PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

		int[][] f = new int[111][111];
		int[] y = new int[111];
		int[] a = new int[111];
		int test = cin.nextInt();
		for (int cas = 1; cas <= test; cas++) {
			cout.print("Case " + cas + ": ");
			int n = cin.nextInt();
			int w = cin.nextInt();
			int k = cin.nextInt();
			for (int i = 0; i < n; i++) {
				cin.nextInt();
				y[i] = cin.nextInt();
			}
			Arrays.sort(y, 0, n);
			for (int i = n - 1; i >= 0; i--) {
				int high = i, low = i;
				while (low >= 0 && y[high] - y[low] <= w)
					low--;
				a[i] = high - low;
			}
			for (int i = 0; i < n; i++) {
				for (int j = 1; j <= k; j++) {
					if (i >= a[i])
						f[i][j] = Math.max(f[i - 1][j], f[i - a[i]][j - 1]
								+ a[i]);
					else
						f[i][j] = a[i];
				}
			}
			cout.println(f[n - 1][k]);
		}

		cout.flush();
	}

	public static void main(String args[]) {
		new P1017().run();
	}

	class Scanner {

		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			eat("");
		}

		void eat(String s) {
			st = new StringTokenizer(s);
		}

		String nextLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
				throw new IOError(e);
			}
		}

		boolean hasNext() {
			while (!st.hasMoreTokens()) {
				String s = nextLine();
				if (s == null)
					return false;
				eat(s);
			}
			return true;
		}

		String next() {
			hasNext();
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

}