ABC 401-500/ABC408D - Flip to Gather - 競技プログラミング用 知識集積所

---

問題

ABC408D

必要知識

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

• 動的計画法（未作成）

考え方

状態を「0だけ」「1並び継続中」「1並び終了済」の3つに分けて考える。
前からi文字をそれぞれの条件の文字列にする、その最小手数を動的計画法（未作成）で求めればよい。

• 「0だけ」は「0だけ」に0をくっつけるしかない
• 「1並び継続中」は「0だけ」か「1並び継続中」に1をくっつける
• 「1並び終了済」は「1並び継続中」か「1並び終了済」に0をくっつける

をミスなく考察できるかが勝負。

解答例

解答例

注意点

別解