AtCoder Beginner Contest 251 E問題 Tahakashi and Animals
問題
提出解答
問題の概要
集合 があり, 最初, である.
次の操作を好きなだけ行なう.
- 円払い, に を加える.
- 円払い, に を加える.
- 円払い, に を加える.
- 円払い, に を加える.
- 円払い, に を加える.
- 円払い, に を加える.
にするためには最低何円必要か?
制約
解法1
「 円払い, に を加える.」という操作を操作 ということにする.
このとき,
- にするためには, 操作 と操作 のうちのどちらか一方を行わければならない (操作 は操作 とする).
ということになる. ここで, のときは とつながっているが, のときは であるというこから, ここに着目する. より詳しく, 操作 をするかどうかで場合分けする.
解法2
操作 をしない場合, 次の動的計画法 を考える.
- =] 操作 まで見た時, 要求を満たし, しかも操作 を ならばしない, ならばする操作達の費用の最小値
このとき, ベースケースは操作 をしないということに着目すると,
である. 遷移式は操作 を続けてしないということはできないということに着目すると,
である. この場合の答えは, 操作 は必ずしないといけないので, である.
解法3
操作 をする場合は上と同様にして求めることができるが, 次の部分が異なる (動的計画法は とする).
- ベースケースは である.
- 遷移式は上と同様である.
- 最終解答は操作 はやってもやらなくてもいいので, である.
解法4
以上から, 操作 をするかしないかで場合分けし, 各場合における最小費用を求めたので, この2つのうちの小さい方が最終解答になる.