要求された金額を超えないように、手持ちのお金を支払うとき、支払える最大金額を答えよ、という問題。 要求金額は100K程度で、通貨の種類が10程度、通貨の枚数は1000程度。普通にDPをやると多分TLEするので工夫が必要。K種類の通貨で実現できる金額がすべて…

N地点についてそれぞれの間の距離が与えられるので、すべてが連結されるようにできるだけ小さいコストでつなぐときの最小距離を求めよ、という問題。 典型的なMSTなのでプリムなりクラスカルなり...。