Description
给出两个长度为n的01串s和t 你进行若干次操作，每次操作可以更改s中某一个位置上的值，每次操作前后需要保证s中不存在相邻3个一样的字符 现在问把s变为t所需要的最小操作次数 n<=5000
Solution
niubi题 我们在0->1之间画一条红线，在1->0之间画一条蓝线 默认字符串开头结尾有无限多的红蓝线，我们可以发现两个字符串相等等价于这两个字符串的红蓝线相等 然后会发现更改一个位置上的数相当于将一条红蓝线左移/右移 并且时时刻刻相邻红蓝线之间的距离<=2 那么我们可以直接枚举红蓝线之间的对应关系暴力计算答案
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std
;
const int N
=2e4+5;
int n
,a
[N
],b
[N
];
char s
[N
],t
[N
];
int calc() {
int t1
=0,t2
=0;
fo(i
,1,n
-1) if (s
[i
]=='0'&&s
[i
+1]=='1') a
[++t1
]=i
;
fo(i
,1,n
) b
[++t2
]=0;
fo(i
,1,n
-1) if (t
[i
]=='0'&&t
[i
+1]=='1') b
[++t2
]=i
;
fo(i
,1,n
) b
[++t2
]=n
;
int ret
=n
*n
;
fo(i
,1,t2
-t1
+1) {
int now
=0;
fo(j
,1,i
-1) now
+=b
[j
];
fo(j
,1,t1
) now
+=abs(a
[j
]-b
[i
+j
-1]);
fo(j
,i
+t1
,t2
) now
+=n
-b
[j
];
ret
=min(ret
,now
);
}
return ret
;
}
int main() {
scanf("%d",&n
);scanf("%s",s
+1);scanf("%s",t
+1);
if (n
<=2) {
int ans
=0;
fo(i
,1,n
) ans
+=s
[i
]!=t
[i
];
printf("%d\n",ans
);
return 0;
}
int tmp
=calc();
fo(i
,1,n
) s
[i
]='0'+'1'-s
[i
],t
[i
]='0'+'1'-t
[i
];
printf("%d\n",tmp
+calc());
return 0;
}
