1276

要求された金額を超えないように、手持ちのお金を支払うとき、支払える最大金額を答えよ、という問題。

要求金額は100K程度で、通貨の種類が10程度、通貨の枚数は1000程度。普通にDPをやると多分TLEするので工夫が必要。K種類の通貨で実現できる金額がすべて分かっているのであれば、K+1種類の通貨で実現できる金額は、それに対してK+1種類目で実現できる金額を加えたもの。これを全通り試すと効率が悪いので、実現できる金額を上から見ていく。たとえばMという額がK種類で達成できているときに、K+1種類目の額面がCだとすると、M,M+C,M+C+C,...が達成できるわけであるが、既にM+Cが達成済みと分かれば後ろは見なくて良いことになる。(M+CがK種類で達成されていることから、それに対してK+1種類目を適用した分は探索済みである。)

後はDPの表を埋めて、最大金額を答えればおしまい。