yukicoder 158 奇妙なお使い

問題

http://yukicoder.me/problems/125

解法

DP.

f(i,j,k) : 1000円をi枚 100円をj個 1円をk個持ってるときにいける回数とする.

1000円を沢山持ってると後々で困ったりするので、Db円やDc円を払うときは1000円、100円を出来るだけ使うようにする必要がある。つまり払うときの枚数は貪欲にすれば良い。なので、(i,j,k)持ってるときに

・Bさんのとこに行った後の枚数(ib,jb,kb)

・Cさんのとこに行った後の枚数(ic,jc,kc)

を求めると

f(i,j,k) = max(f(ib,jb,kb),f(ic,jc,kc))+1

とすれば求まる。