きままにものづくり

日々の気付いたことなんかを書いてます。

ARC033 C問題

問題


C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder

解法

辞書順の制限が無いの場合は、終了時間が早い順に選んでいく貪欲法で解くことができる。
辞書順の制限がある場合は動的計画法を用いることで解ける。
以下のようなdpを考える。
 dp[時間] = (完了仕事数, インデックス)
これを後ろの時間から埋めていくことで、dp[0]での完了仕事数が答えとなる。インデックスと終了時間を対応付ける配列を作成しておくことで、経路をたどることができる。
dpは完了仕事数が最大かつインデックスが最小となるように更新する。

計算量

 O(N)

コード

広告を非表示にする