题意分析
给定长度为 $n$ 的 $01$ 串 $s,t$，可以对 $s$ 执行三个操作：
- 将 $s_l,s_{l+1},s_{l+2},\cdots,s_r$ 均改为 $0$，记为
OFF操作。 - 将 $s_l,s_{l+1},s_{l+2},\cdots,s_r$ 均改为 $1$，记为
ON操作。 - 翻转 $s_l,s_{l+1},s_{l+2},\cdots,s_r$，记为
TOG操作。
求最小操作次数。
考虑 DP 状态及转移。
对于 $s_i$，其最终受到的操作状态只能是：
- 未操作。
TOG，$s_i$ 被翻转一次。OFF，$s_i$ 为 $0$。ON，$s_i$ 为 $1$。OFF&TOG。即先OFF再TOG，$s_i$ 为 $1$。ON&TOG。即先ON再TOG，$s_i$ 为 $0$。
关于操作顺序问题
对于 ON 和 OFF 操作，对于一个元素只需要操作一次。否则前几次都是无意义的（会被覆盖）。
对于 TOG 操作，TOG 之后被 ON 或 OFF 操作覆盖也是无意义的，因此只能在这两个操作之后进行。而两次 TOG 操作也是无意义的。
这样，每个元素至多进行两次操作。
于是就可以 DP 了。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e6;
//0:未操作,1:TOG,2:OFF,3:ON,4:OFF&TOG,5:ON&TOG
int n,dp[N+1][6];
char s[N+1],t[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>(s+1)>>(t+1);
n=strlen(s+1);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
dp[0][1]=dp[0][2]=dp[0][3]=1;
dp[0][4]=dp[0][5]=2;
for(int i=1;i<=n;i++){
if(s[i]==t[i]){
dp[i][0]=dp[i-1][0];
for(int j=1;j<=5;j++){
dp[i][0]=min(dp[i][0],dp[i-1][j]);
}
}else{
dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]);
dp[i][1]=min(dp[i][1],dp[i-1][2]+1);
dp[i][1]=min(dp[i][1],dp[i-1][3]+1);
dp[i][1]=min(dp[i][1],dp[i-1][4]);
dp[i][1]=min(dp[i][1],dp[i-1][5]);
}
if(t[i]=='0'){
dp[i][2]=min(dp[i-1][0]+1,dp[i-1][1]+1);
dp[i][2]=min(dp[i][2],dp[i-1][2]);
dp[i][2]=min(dp[i][2],dp[i-1][3]+1);
dp[i][2]=min(dp[i][2],dp[i-1][4]);
dp[i][2]=min(dp[i][2],dp[i-1][5]+1);
dp[i][5]=min(dp[i-1][0]+2,dp[i-1][1]+1);
dp[i][5]=min(dp[i][5],dp[i-1][2]+2);
dp[i][5]=min(dp[i][5],dp[i-1][3]+1);
dp[i][5]=min(dp[i][5],dp[i-1][4]+1);
dp[i][5]=min(dp[i][5],dp[i-1][5]);
}else{
dp[i][3]=min(dp[i-1][0]+1,dp[i-1][1]+1);
dp[i][3]=min(dp[i][3],dp[i-1][2]+1);
dp[i][3]=min(dp[i][3],dp[i-1][3]);
dp[i][3]=min(dp[i][3],dp[i-1][4]+1);
dp[i][3]=min(dp[i][3],dp[i-1][5]);
dp[i][4]=min(dp[i-1][0]+2,dp[i-1][1]+1);
dp[i][4]=min(dp[i][4],dp[i-1][2]+1);
dp[i][4]=min(dp[i][4],dp[i-1][3]+2);
dp[i][4]=min(dp[i][4],dp[i-1][4]);
dp[i][4]=min(dp[i][4],dp[i-1][5]+1);
}
}
int ans=2147483647;
for(int i=0;i<=5;i++){
ans=min(ans,dp[n][i]);
}
cout<<ans<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
