2015年3月2日月曜日

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
とすれば求まる。

0 件のコメント:

コメントを投稿