woj_momodi.java

第四届百度杯预赛解题报告 武汉大学20090315

import java.util.Scanner;

public class WOJ {
	static int N, T;
	static int[] cost;
	static int[][] dp;
	static Scanner cin = new Scanner(System.in);

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ca = cin.nextInt();
		while (ca-- > 0) {
			N = cin.nextInt();
			T = cin.nextInt();
			if (N == 0 && T == 0) {
			}
			cost = new int[N];
			for (int i = 0; i < N; ++i) {
				cost[i] = cin.nextInt();
			}
			System.out.println(solve());
		}
	}

	static int solve() {
		dp = new int[N + 1][];
		for (int i = 0; i <= N; ++i) {
			dp[i] = new int[T + 1];
		}
		for (int i = 1; i <= N; ++i) {
			int sum = 0;
			for (int j = 0; j <= T; ++j) {
				dp[i][j] = dp[i - 1][j];
			}
			for (int j = i; j >= 1; --j) {
				sum += cost[j - 1];
				if (sum > T) {
					break;
				}
				int add = (i - j + 1) * (i - j + 1);
				for (int t = T - sum; t >= 0; --t) {
					if (dp[j - 1][t] + add > dp[i][t + sum]) {
						dp[i][t + sum] = dp[j - 1][t] + add;
					}
				}
			}
		}
		return dp[N][T];
	}
}