導入
atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。
使用しているアルゴリズム
- 動的計画法（DP）
解法のポイント
この問題は「締切と作業時間のあるタスク」を選んで報酬の総和を最大化する典型的なスケジューリング問題です。
DPテーブル dp[i][j] は、タスクを期限順にソートした i 番目まで見たとき、j 日目までで得られる報酬の最大値を表します。
以下、解法のポイントをざっくりと。
- タスクは
(l, d, a)という形式で、締切l、所要日数d、報酬a。 - 締切順にタスクを並べることで、DPで「そのタスクをやる/やらない」の選択がしやすくなります。
- 各タスクに対して、可能な日数
jを逆順でループすることで、「j - d 日前に終わっているなら実行できる」かどうかを簡単に判定できます。 -
dp[i][j] = max(dp[i-1][j-d] + a, dp[i-1][j])のように、タスクをこなした場合とスキップした場合の最大を取って更新します。
最終的な答えは、全タスクを見たあとの dp[-1] の中で最大の値です。
具体的なDPイメージ
問題の入力例2の場合、以下のようなDPになります。
3
7 3 200000
3 2 100000
5 3 150000
| タスク数 \ 日数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (標準入力2番目) | 0 | 0 | 100000 | 100000 | 0 | 0 | 0 | 0 |
| 2 (標準入力3番目) | 0 | 0 | 100000 | 150000 | 150000 | 250000 | 0 | 0 |
| 3 (標準入力1番目) | 0 | 0 | 100000 | 200000 | 200000 | 300000 | 350000 | 350000 |
ACサンプル
# dp[i][j]: iを標準入力で与えられたタスクを期限順にソートしたindex, jをj日目と考える
## つまり、dp[i][j]にはiタスク目のj日目で取れる最大の報酬総額を入れる
## 逆に標準入力で与えられたタスクを期限順にソートしなければdpは使えない
N = int(input())
tasks = [(l,d,a) for l,d,a in (map(int, input().split()) for _ in range(N))]
tasks.sort(key=lambda x: x[0])
# dp[i][j]のjの末端はmax(tasks, key=lambda x: x[0])[0]になる:: あ、tasks[-1][0]でもいけるわ
max_l = max(tasks, key=lambda x: x[0])[0]
dp = [[0] * (max_l + 1) for _ in range(N+1)]
for i in range(1,N+1):
l,d,a = tasks[i-1]
# そのタスクの期限から逆順に辿ることで斬化式が単純化できる
for j in range(l, -1,-1):
if j - d >= 0:
# 単純化された斬化式
dp[i][j] = max(dp[i-1][j - d] + a, dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
# iを標準入力で与えられたタスクを期限順にソートしているのでdp[-1]の最大値が答えになる
print(max(dp[-1]))