11/14 PKU - Algorithmer’s note

コインが何種類かあって、ある品物を買うのに、「払ったコインの枚数」と「おつりの枚数」の合計が最小になる方法で買いたい。おつりは最も枚数が少なくなるように返される。払うことができるコインの枚数には限界があるが、おつりではこの制限はない。この合計の最小値を求めよ。

ある金額を払うために必要なコインの枚数と、ある金額を返すために必要なコインの枚数を、十分大きい金額まで計算するだけ

牛が１日をN部分に分けた。各部分ごとに、寝た時の効率が決まっている。寝るときには、寝始めの部分では効率の数値を得られず、その後の部分において効率の数値を得られる。時間はループするので、N部分目の次は1部分目である。最も効率を得るときの値を求めよ。

ループがなければただのDP。ループするのがわりとやっかいだが、「1部分目から寝て効率を得ている」なら「N部分目で寝た状態に入ればいい」ことがわかる。「1部分目では起きてるか、寝始める」なら「N部分目では寝てても起きててもよい」から、2回DPするだけ。