ABC 401-500/ABC441F - Must Buy - 競技プログラミング用 知識集積所

---

問題

ABC441F

必要知識

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

• 動的計画法
• バックトレース

考え方

ベースは、基本的なナップサック問題。（DP-D参照）
ここに、「そのデータは最終的な答えに使われうるか？」の情報を追加するだけ。

つまり、DPテーブルを更新する際に、その商品を「使うか使わないか両方可か」を記録しておく。
全部埋め終わったら、バックトレースしながら、DPテーブル上のその情報を使う可能性があるかどうかをtrue/falseで記録していく。
その際についでに「使うか使わないか両方可か」にどんな情報が出てきたか見ながら、解答すべき文字を1つずつ決定すればよい。

あとは実装力勝負。

解答例

解答例

注意点

long long型を使う。

価値合計はint型範囲を超えることがあるので注意。

別解