Codeforces Round #490 (Div. 3)F. Cards and Joy

問題概要

長さ n\times k の数列があり, i 番目の要素は c_i である. 

この数字を n 人に k 個ずつ配る. i 番目の人は数字 f_i を好んでおり, 配られた数字の中の f_i の個数が t ならば幸福度 h_t を得る.

自由に数列を配れるとき, 全体の幸福度の最大値はいくらか？

問題へのリンク

制約

  • 1 \le n \le 500, 1 \le k \le 10
  • 1 \le f_i \le 10^5
  • 1 \le h_i \le 10^5

解法

数字 f を好む人に, あるだけ f を配るのが最適なのはすぐわかります. では, 数字 f を好む人が p 人いて, 数字 f が q 個あるとき, 得られる最大値はいくらでしょうか？

一人 k 枚までしか配ることができないので, p\times k \le q のとき明らかに幸福度の最大は h_k  \times p です( p 人全員に f を k 個ずつ配ることができます). これを満たさない場合を考えましょう.

dp[i][j] := (i 人に k 個の数字を配るときの幸福度の最大値) としましょう. 遷移を考えれば, i+1 人目に 数字を 0\sim k 個配る場合それぞれについて考えれば良いですから,  

dp[i+1][j] = max_{0 \le p \le k}(dp[i][j-p])

となります. この dp テーブルは O(n^2k^2) で埋められることがわかります. 

これさえできれば, 各数字の個数とそれを欲している人数を std::map などで管理すれば, 答えを求めることができます.

実装

Submission #147254690 - Codeforces