JOI2011本選 B - 古本屋 (Books) - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

買い取り価格 ${1\le C_i\le 10^5}$ 円の本が ${2\le N\le 2000}$ 冊与えられる. 本にはそれぞれジャンル ${1\le G_i\le 10}$ のジャンルが決まっていて同ジャンルの本を ${T}$ 冊売ると, そのジャンルの本の買い取り価格が ${1}$ 冊につき ${T-1}$ 円上がる. ${N}$ 冊の本から ${1\le K\lt N}$ 冊選んで売るときの最大買い取り価格を答えよ.

思考の流れ

同じジャンルの本を売るときは高いものから売るというのはすぐにわかる. 各ジャンルについていくつ売るかを決めると価格は決まるので, 売る数を探索したくなるが, 数が多すぎて無理.

${\downarrow}$

あるジャンルの本を ${i}$ 冊売ると決めると, その買い取り価格は ${S_{i}+T(T-1)}$ ( ${S_{i}}$ はそのジャンルの買い取り価格が高い ${i}$ 冊の買い取り価格の合計)となるので, 各ジャンルに対して「 ${i}$ 冊売るときの買い取り価格の最大値」を求めておく. これを
売る本の数＝重さ
買い取り価格＝価値
とみるとナップサック問題と考えることができる. ただし, ナップサック問題とは違い各ジャンル一つしか選ぶことができないという条件に注意する.