ABC275F 解法 \(a_{i}\) を残すとき 0, 消すとき 1 として,01 列を考える. 1 が連続している区間の個数を最小化する問題となる. 区間を数える代わりに,[01] の並びを数えると考えるとよい. [11], [00], [10] は数えないとする. つまり,01 列において [01] の並びの個数が 1 の区間の個数と 1対1 対応する. これを踏まえれば,次の dp が作れる. \(dp_{i,s,k} := \) \(a_{[0,i)}\) において, 合計が \(s\) かつ 最後が \(k \in 2\) のときの min. ここで,\(a_{-1} = 0\)…