uva12545 Bits Equalizer（求最小操作数）

题目简述：

有两个长度相同的字符串
字符串s1包含0、1、？
字符串s2包含0、1
然后我们对s1中的字符可以进行如下三种操作：
1.把0变1
2.把？变0或1
3.交换任意两个字符
求将s1变换为s2的最小操作数

方便起见，给s1的每个字符标号a、b、c、d……，变换操作即为改变某标定字符的值，交换操作即为交换两个标定字符的位置，比如标定s1为abcd，交换ac后得到cbad。
下面将这每个标定了的字符称为“字母”。
如此，任意一种操作可以记为<类型，字母1[，字母2]>。

然后给出一些结论：

1. 在任意的某个操作序列中，可以将任意的变换操作任意调整位置而不影响最终得到的结果。
2. 最优解操作序列中，任意的字母最多出现于1个交换类型的操作中。

关于结论2，证明如下：
先依据结论1，把最优解序列调整为变换全部在前，交换全部在后。然后我们可以证明，任意两个相邻的交换操作所涉及的4个字母各不相同，否则设A<交换，a，b>、B<交换，a，c>是两个相邻的交换操作，a、b、c非0即1，要避免无意义的交换，所以a、b不同，a、c不同，不妨设abc=011，经过操作A、B后，abc变为bca，这两个操作对字符串产生的影响是原来011的三个位置变成了110，但是我们可以仅通过交换a、c来达到同样的结果，所以若这样的A、B相邻，那么一定不是最优解。从而最优解的交换序列中任意两个操作对象不重复，既然不重复，那么这两个操作就可以交换次序，结果等效，如此我们得到的操作序列仍是一个最优解，所以仍然满足相邻不重复。所以我们得到推论：最优解的任意两个交换操作都包含不重复的4个字母，即任意一个字母最多参与1个交换操作。

根据结论2，如果某次交换操作将a调离了原本位置，将b调了过来，那么接下来所有的交换操作都不会涉及b现在这个位置，即不仅仅是字母最多只参与一次交换操作，而且字符串中的每个位置最多也只参与1次交换操作。

所以最优解中，任意一个位置前前后后最多经历2个操作，先变换一次，再交换一次。

下面分析问题本身。
不配对的可以分为这样四种：

那么交换操作一共有3种类型：AD、AB、CD（容易知道BC不会出现在最优解里）。
AB这种交换一定是和？变换为0绑定的，CD这种一定是和？变换为1绑定的，AD这种交换一定不存在变换。所以我们将操作这样分类：第一类：B?变1，C中?变0，D中0变1；第二类：B中?变0+AB交换，C中?变1+CD交换；第三类：AD交换。如此等于说我们把操作序列重排并且划分成片段，每个片段包含一个或两个操作，这样划分的结果是片段与片段之间的操作对象完全不重复，即无需证明即可知这些片段可以任意调整次序，如此我们可以有底气地用局部最优解来替代全局最优解。可见第一类、第二类消除不匹配对数的能力为1，即一步操作消除1对，而第三类消除不匹配对数的能力为2。
由于片段间彼此独立，我们把所有的第三类片段提前，考虑首先能进行多少个第三类的片段，第三类最多配对即为最优解的方案，故优先考虑AD的配对，如果D中有剩余的0，再考虑第一类或第二类操作（这时采用第一类或第二类无所谓，因为它们消除能力是一样的）。