令 $f_{i,0/1,0/1}$ 表示考虑到第 $i$ 位，交换后 $s_1$ 第 $i$ 位为 $0/1$，$s_2$ 第 $i$ 位为 $0/1$。然后分四种情况讨论：

1. 两个串都不交换：

   $f_{i,s_{1,i},s_{2,i}}=\max(f_{i-1,0,0},f_{i-1,0,1},f_{i-1,1,0},f_{i-1,1,1})+[s_{1,i}=s_{2,i}]$

2. 交换 $s_1$ 的第 $i$ 位和本次交换前的最后一位： $f_{i,0,s_{2,i}}=\max(f_{i-1,0,0}+[s_{1,i}=0]+[s_{2,i}=0]-1,f_{i-1,0,1}+[s_{1,i}=1]+[s_{2,i}=0])$ $f_{i,1,s_{2,i}}=\max(f_{i-1,1,0}+[s_{1,i}=0]+[s_{2,i}=1],f_{i-1,1,1}+[s_{1,i}=1]+[s_{2,i}=1]-1)$ 其中 $-1$ 是拆散了之前匹配的 $(0,0)$ 或 $(1,1)$，前提是 $t_{1,i}=t_{1,i-1}=1$。

3. 交换 $s_2$ 的第 $i$ 位和本次交换前的最后一位： $f_{i,s_{1,i},0}=\max(f_{i-1,0,0}+[s_{1,i}=0]+[s_{2,i}=0]-1,f_{i-1,1,0}+[s_{1,i}=0]+[s_{2,i}=1])$ $f_{i,s_{1,i},1}=\max(f_{i-1,0,1}+[s_{1,i}=1]+[s_{2,i}=0],f_{i-1,1,1}+[s_{1,i}=1]+[s_{2,i}=1]-1)$ 前提是 $t_{2,i}=t_{2,i-1}=1$。

4. 两组都交换： $f_{i,0,0}=f_{i-1,0,0}+[s_{1,i}=s_{2,i}]$ $f_{i,0,1}=f_{i-1,0,1}+[s_{1,i}=s_{2,i}]$ $f_{i,1,0}=f_{i-1,1,0}+[s_{1,i}=s_{2,i}]$ $f_{i,1,1}=f_{i-1,1,1}+[s_{1,i}=s_{2,i}]$ 前提是 $t_{1,i}=t_{1,i-1}=t_{2,i}=t_{2,i-1}=1$。

最终只过了前五组大样例。