2020/08/15

映画を見た。

競プロ

• AtCoder 4AC

C - 最高のトッピングにしような

解説AC 45分

いい問題だった。DPの状態量が減らせずに答えを見たが、結局スペシャルチケットを1枚ずつ使うことで最大個分のトッピングがもらえるので、チケットの種類は無視した上で、今までにとったトッピングの値がを超えないように考えれば良いという話。

こういう系の状態量を落とせない系のDPは、部分的に貪欲っぽい発想をすれば良いことが多いので記憶しておく。