https://atcoder.jp/contests/abc017/tasks/abc017_4

  • Thoughts.
    • Take them in numerical order, do not take the same flavor, you must take at least one.
    • If you are done up to k pieces and then the next day, the past information is no longer relevant, so f(k)
    • Since the range sum of the f in front is required to the extent that there is no flavor overlap DP with cumulative sum.
    • Record the last appearance of each flavor to determine the range.
  • Official Explanation
    • In addition to DP with cumulative summing, there is also the idea of [inchworm law

This page is auto-translated from /nishio/abc017_4 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.