ABC 401-500/ABC440E - Cookies - 競技プログラミング用 知識集積所

---

問題

ABC440E

必要知識

B以下レベルの内容は省略

• 動的計画法

考え方

クッキーの種類数が最大50と少ないので、クッキーの種類を1つずつ増やしていく動的計画法で間に合う。
1種類クッキーを追加するごとに、最高のクッキーを新規追加したクッキーに任意の個数変えることで、全てのクッキーの選び方を網羅できる。
そして、最善からX通りだけを保存して次に継承することで、最終的にO(N*X*logX)で解決する。

データ構造は、良い方から一定数だけ取り出したい+途中で追加もありうるということで、priority_queue※を採用する。
ここに「評価、最高のクッキーの個数」という形でデータを入れていく。
データを1つ取り出すごとに、

• 次に継承するデータに追加する
• 最高クッキーを新規クッキーに変更したデータを元のpriority_queue※に追加

の2つをやっていくことで、その種類までで評価が高い方からX通りが入ったpriority_queue※を作ることができる。

解答例

解答例

注意点

long long型が必要。

答えはint型を大きく超えることがある。
priority_queue※を含め、long long型を適切に用いること。

別解