読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 502 Div1 Medium: TheProgrammingContestDivOne

解法

動的計画法で解く、いわゆる典型DP。

requiredTime/pointsPerMinが小さい方から解いていく方が有利なので、問題をこの値でソートし、DPすれば良い。

コード

import java.util.Arrays;

public class TheProgrammingContestDivOne {

	public int find(int T, int[] maxPoints, int[] pPerMin, int[] requiredTime) {
		int N = maxPoints.length;
		Problem[] p = new Problem[N];
		for (int i = 0; i < N; i++) {
			p[i] = new Problem(maxPoints[i], pPerMin[i], requiredTime[i]);
		}
		Arrays.sort(p);

		int[][] dp = new int[N + 1][T + 1];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= T; j++) {
				dp[i + 1][j] = dp[i][j];
			}
			for (int time = p[i].require; time <= T; time++) {
				long x = p[i].max - (long) p[i].ppm * time;
				if (x > 0) {
					int prevTime = time - p[i].require;
					int nextPoint = dp[i][prevTime] + (int) x;
					dp[i + 1][time] = Math.max(dp[i + 1][time], nextPoint);
				}
			}
		}

		int max = 0;
		for (int i = 0; i <= T; i++) {
			max = Math.max(max, dp[N][i]);
		}
		return max;
	}
}

class Problem implements Comparable<Problem> {
	int max, ppm, require;

	public Problem(int max, int ppm, int require) {
		this.max = max;
		this.ppm = ppm;
		this.require = require;
	}

	@Override
	public int compareTo(Problem o) {
		return Long.signum((long) this.require * o.ppm - (long) o.require
				* this.ppm);
	}
}