どのような文字列が途中の状態としてありえるかを考えてみます．隣り合う文字が異なる場所の個数を最小化します．

writer 解説と同様の考察で，始点と終点でどの 0, 1が対応しているかを考えたときに，始点と終点で前後の位置関係が変化するような組については前後がどちらになっていてもよく，位置関係が同じである組についてはその順番を崩せない，ということがわかります．

以上の考察で，文字列を0で区切って考えたとき，各1がどの区間に存在できるかを求めます．各1をどの区間に存在するようかを決めたとき，各区間に1が存在するかどうかで，

• 先頭の0の前，末尾の0の後はコスト1
• それ以外の区間はコスト2

がかかるときの合計コストの最小値はいくつか，と言い換えることができます．

重みが全部同じときは区間の終端でソートしてすでにその区間に1がなければ一番後ろに1を置く，という方針で最適解が得られます．

先頭を使うかどうかで場合分けすれば，同様の方針でそれぞれの場合の最適解が得られます．

適切に実装すれば時間計算量は \(\mathrm{O}(N)\) です．