ABC 401-500/ABC431D - Robot Customize - 競技プログラミング用 知識集積所

---

問題

ABC431D

問題文が説明不足で、2通りの解釈ができる。
というのは、

高橋くんは、N種類の部品をすべて1個ずつロボットに取り付けたいと思っています。
ロボットを倒さないように部品を取り付けたとき、（略）

という言い方が、

• すべての種類の個数が1個になるように取り付けたいと思っています。そのように全て取り付けた状態でロボットが倒れてしまわないように（略）
• すべての種類のものを、1個ずつ順番に取り付けたいと思っています。途中でロボットを倒さないようにしながらそのように取り付けたとき、（略）

というどちらにも解釈できるため。

順番は番号順なのか好きな順でつけていいのか、のような記述がない点が、後者を意図しているとしたらやや不自然か？　とは考えられるが、しかし明確な判断基準にできる記述もない。
一応、前者の想定で書いたコードがACしたので、前者の理解でいいらしい。

なお、後者で考えたとしても、好きな順で取り付けていいと判断するなら解法は同じとなる。

必要知識

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

• 動的計画法

考え方

パーツを体につけるか頭につけるかで価値が変わるというのは面倒。
そこで、まず全部体に付けた後、いくつかを頭に移動させることを考える。
すると、ただのナップサック問題になり、DPまとめコンテスト/D - Knapsack 1とほぼ同等のものになる。

問題は頭に移動すると幸福度が下がる場合があり、通常のナップサック問題でいう価値がマイナスの品があること。
しかし、このようなものは頭に移動することが絶対にないので、最初から移動候補から除外してしまうことで対策できる。

解答例

解答例
メモリ使用量が不安な場合は、一次元のvectorで動的計画法を書くこともできる。

注意点

解答にはlong long型を使用する。

入力例にあるように、答えはint型に入らないことがあるので注意。

別解