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);
一見すると注文限界時間Tに余裕を持たせ、配るDPをすることで最後の注文に対応できるようにも思えるが、maxで更新されてしまうので現実は理想的には行かない。
かといって、任意のfood[i]を取り除いたDPを工夫せずに全て試すとになってしまうので、工夫が必要になる。具体的には予め通常DPと逆順DPを用意しておき、ans = max (ans, food[i]の上側T1までのDP最大値 + food[i]の下側T2までのDP最大値 + food[i]) で最大値 (T1 + T2 = T) を計算する。この工夫により、計算量は
に減らせる。通常DPと逆順DPを用意するため、商品リストの先頭と末尾にダミーを追加しておくと実装しやすくなる。
