IOI饅頭(14本選2)

N個の饅頭があり、それぞれ価格が決まっている。

M個の箱があり、それぞれ何個饅頭を入れられるか、購入の際のコストが決まっている。

利益を最大化しようという問題。

まず、饅頭をi個売る時は、高いもの時からi個売るのがいいので、ソートして累積和を求めて置く。

次に、DP[i個目の箱までで[j個以下饅頭を詰められるときの]費用の最小値を求める。

最後に饅頭を売る数で全探索する。

計算量はO(NM)

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

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