题解

思路

交换不会改变零和一的数量。设零的数量为 $z$、一的数量为 $o$，则任意两个不同字符构成的下标对恰好属于 01 或 10，总数为 $zo$。平衡目标因此要求两类各有 $zo/2$ 个；题目保证该值为整数且可达。

任意目标串与原串中不同的位置数必为偶数。每次交换一个错放的零和一个错放的一，恰好修正两个位置，所以到某个目标串的最少交换次数是汉明距离的一半。

做法

从左到右构造目标串。设已经放置了 $j$ 个一，并已经产生 $p$ 个 01 对。若当前位置放零，$p$ 不变；若放一，它与前面所有 $i-j$ 个零各形成一个 01 对，故 $p$ 增加 $i-j$。转移代价是新字符是否与原字符不同。

最终要求恰好放置 $o$ 个一且 $p=zo/2$。DP 最小代价除以二即为答案。

$|s|\le16$ 时可以枚举所有保留零一数量的目标串；若输入本身平衡，答案直接为零。

正确性说明

DP 的两个计数分别完整记录目标串一的数量与 01 数量，每个位置恰好选择零或一，因此它枚举了所有零一数量不变的目标串。终态约束又恰好等价于平衡。DP 代价等于目标串与原串的汉明距离，而同数量二进制串之间的最少任意交换次数恰为汉明距离的一半。因此 DP 终态的最小代价除以二就是最少操作数。

复杂度

时间复杂度为 $O(n^2zo)=O(n^4)$ 的状态上界写法；利用位置限制后的实际状态数为 $O(n\cdot o\cdot zo)$，在 $n\le100$ 时至多约 $2.5\times10^7$ 次转移。空间复杂度为 $O(o\cdot zo)$。