古本屋(11本選2)

N冊の本の中からK冊本を売る。

各本には値段とジャンルが決まっていて、同じジャンルの本を多く売るとボーナスが入るので、利益の最大値を求めようという問題。

まず、任意のジャンルに関して、高いものから売ればより高くなることはすぐにわかるのでソートしておく。

また、これによって各ジャンルについて、売った冊数から売価を求められる。

その結果を利用し、

dp[iジャンル目までで][j冊売った]時の利益の最大値

というdpを回せばよい。計算量はO(N^2)

難易度は7程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2286172#1