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.