7K12 blog

猫でも分かるアルゴリズム解説

ABC145 E - All-you-can-eat

f:id:tkr987:20200531192549p:plain
https://atcoder.jp/contests/abc145/submissions/12428154

  • 商品を1個だけ手に持てるナップサックは通常DP逆順DPを組み合わせると暗記
  • 繰り返しは rep(i, 1, Size(nyaa)-1) rep(t, 0, T)
  • 出力は ans = max(ans, dp1[i - 1][t] + dp2[i + 1][T - 1 - t] + nyaa[i].second);

f:id:tkr987:20200531203052p:plain
一見すると注文限界時間Tに余裕を持たせ、配るDPをすることで最後の注文に対応できるようにも思えるが、maxで更新されてしまうので現実は理想的には行かない。

かといって、任意のfood[i]を取り除いたDPを工夫せずに全て試すと O(N \times NT)になってしまうので、工夫が必要になる。具体的には予め通常DPと逆順DPを用意しておき、ans = max (ans, food[i]の上側T1までのDP最大値 + food[i]の下側T2までのDP最大値 + food[i]) で最大値 (T1 + T2 = T) を計算する。この工夫により、計算量は O(NT)に減らせる。通常DPと逆順DPを用意するため、商品リストの先頭と末尾にダミーを追加しておくと実装しやすくなる。