各仕事には締切 D、所要時間 C、報酬 S が与えられます。仕事を締切の昇順に並べ、その順に処理します。dp[t] を、時刻 t までに終了するスケジュールの最大報酬とします。
各仕事を選ぶ場合を考え、t を D から C まで降順に走査して dp[t] = max(dp[t], dp[t - C] + S) と更新します。仕事は締切順に並べて実行できます。順序が逆になっている隣り合う二つの仕事を入れ替えると、締切の早い仕事はより早く終了し、もう一方の完了時刻は変わらないため、どちらの締切も守れます。この交換を繰り返せば、締切の昇順に並べられます。先に処理した仕事の締切はすべて現在の仕事の締切以下なので、時刻 t - C までに終わる以前の仕事のスケジュールの後に現在の仕事を追加すれば、t <= D のとき締切を守れます。この交換論法により、締切順に処理しても実行可能な仕事の選択を漏らしません。
t を降順に走査すると、dp[t - C] は現在の仕事を考慮する前の状態のままなので、同じ仕事を複数回選ぶことはありません。各仕事の処理後に累積最大値（dp[t] = max(dp[t], dp[t - 1])）を伝播させ、状態が「ちょうど t 時間かかる」ではなく「時刻 t までに終了する」ことを表すようにします。答えは dp の最大値です。最大締切を Dmax とすると、時間計算量は O(N * Dmax)、空間計算量は O(Dmax) です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
long value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
static class Job {
int deadline;
int duration;
long reward;
Job(int deadline, int duration, long reward) {
this.deadline = deadline;
this.duration = duration;
this.reward = reward;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
Job[] jobs = new Job[n];
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
int deadline = input.nextInt();
int duration = input.nextInt();
long reward = input.nextLong();
jobs[i] = new Job(deadline, duration, reward);
maxDeadline = Math.max(maxDeadline, deadline);
}
Arrays.sort(jobs, Comparator.comparingInt(job -> job.deadline));
long[] dp = new long[maxDeadline + 1];
for (Job job : jobs) {
for (int time = job.deadline; time >= job.duration; time--) {
dp[time] = Math.max(dp[time], dp[time - job.duration] + job.reward);
}
for (int time = 1; time <= maxDeadline; time++) {
dp[time] = Math.max(dp[time], dp[time - 1]);
}
}
long answer = 0;
for (long reward : dp) {
answer = Math.max(answer, reward);
}
System.out.println(answer);
}
}