editorial

D

summary:

A binary string is given. I want to calculate the minimal number of operation(changing the indices of two characters) to make the number of $01$(1 is after 0) and the number of $10$(0 is after 1) equal.

solution:

$d_{i,cnt_0,cnt_{01}}=$ the number of changes if we consider first $i$ characters of $S$ and there is $cnt_0$ zeroes and the number of $01$ is $cnt_{01}$.

The sum of the number of $01$ and $10$ is $cnt_0 \cdot cnt_1$ and they should be equal. The number of $01$ should be $\frac{cnt_0 \cdot cnt_1}{2}$.

The answer is $d_{n,cnt_0,\frac{cnt_0 \cdot cnt_1}{2}}$.