2011JOI本選2 古本屋 解説

問題リンク

解説

それぞれのジャンルごとに売る冊数を決めたとき、ジャンルごとの価格の最大値は明らかです。価格の高いものから貪欲に売るのが明らかに最適であるからです。

これを先に求めれば、ジャンルごとに売る冊数を適切に決めるだけで価格の最大値が求められます。 この、ジャンルごとの冊数を決めるパートでは動的計画法が役立ちます。

ジャンルを順に決めていき、今までに売った冊数をもうひとつの添字に持てば動的計画法で答えが求められます。

この問題では、まず「ジャンルごとに考える」ことが重要になります。違うジャンルの本は、それぞれの買取価格に影響を与えないからです。 その上で、貪欲法で候補を絞った後に動的計画法で答えが求められました。

このように、動的計画法を使う問題でも、順番を適切にソートしたり、貪欲法を先に部分的に使って、動的計画法が使える形に落とす場合があります。