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