解法
動的計画法で解く、いわゆる典型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);
}
}