零一串（困难版）题解

思路

只有 $a_i\ne b_i$ 的位置需要被翻转。每次操作恰好翻转两个位置，因此失配数为奇数时无解。

失配数很小时，可以把每个失配位置看成一个点，用状态压缩枚举它与哪个点配对。若两个失配位置相邻，直接配对代价为 $x$；否则可以花 $y$ 直接翻转，或用相邻操作逐步移动，取两者较小。仅剩一对相邻失配时，还可以借助两个辅助位置做两次非相邻操作，所以代价是 $\min(x,2y)$。

当 $x\ge y$ 时，除“恰好两个相邻失配”外，总能把失配位置两两用代价 $y$ 的操作消去，答案为失配数的一半乘 $y$。

一般情形只需按位置排序失配点。把代价扩大两倍：可以花 $2x(p_i-p_{i-1})$ 配对相邻的两个失配点，也可以花 $y$ 暂时处理一个失配点，两个这样的半步合计为一次代价 $y$ 的配对。由此得到一维动态规划。

做法

记失配位置依次为 $p_0,p_1,\ldots,p_{m-1}$。

1. 若 $m$ 为奇数，输出 $-1$。
2. 若 $m=2$ 且两位置相邻，输出 $\min(x,2y)$。
3. 若 $x\ge y$，输出 $m y/2$。
4. 否则令 $f_i$ 表示处理前 $i$ 个失配点的两倍最小代价。转移为：单独暂存当前点，代价增加 $y$；或把最后两个失配点用相邻操作配对，代价增加 $2x(p_{i-1}-p_{i-2})$。最终输出 $f_m/2$。

复杂度

每组测试扫描字符串并对失配位置做一次线性动态规划，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。