ABC 401-500/ABC442F - Diagonal Separation 2 - 競技プログラミング用 知識集積所

---

問題

ABC442F

必要知識

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

• 動的計画法

考え方

各段が、左からiマスが白マスで残りが黒マス、という状態であり、かつiの値が広義単調減少であればよい。
それに気づけば、あとはわりと典型的な動的計画法。

各段について、「左からiマスに白黒それぞれ何マスあるか」は高速に求められる。
それを用いれば、「左からiマスを白、残りを黒、という状態にするのにその段の何マス塗り替えが必要か」もすぐに求まる。

すると、「その段まで条件が破綻しないように、左からiマス以上を白、残りを黒、という状態にするのにその段以上の何マス塗り替えが必要か」をDPテーブルに持たせれば、答えが求まる。
つまり、j段目のiマス目については

• j-1段目をi個以上白マスにするようにj-1段目まで塗る最少数+j段目をぴったりiマス白くする必要数
• j段目をi+1個以上白マスにするようにj段目まで塗る最少数

の小さい方を新しいデータとすればよい。

解答例

解答例

注意点

別解