J - Sushiで期待値DPを掴んだ気がする

Quiz

https://atcoder.jp/contests/dp/tasks/dp_j

AC

https://atcoder.jp/contests/dp/submissions/8788822

参考

f:id:peroon:20191204215609p:plain

  • サイコロの期待値DPで感覚を掴む
  • 上記画像の最後で書かれている、
    • Σ(Es+x + 1) / 6
    • これは+1部分を外に出すと
    • Σ(Es+x)/6 + 1
    • となり、けんちょんさんのと同じ形になる
  • (遷移元)=(遷移先)+1
  • 今回のSushiに当てはめると、下記のようになる

f:id:peroon:20191204220003p:plain

  • あとはけんちょんさんの通り、式変形で
  • dp[i, j, k] = dp[(i, j, kがより小さい)]
  • の形にしてメモ化再帰すればいい