题意
给定\(n,x,y\)和两个01串，字符串的长度为\(n\)，现在你可以选择一个\(l\)和\(r\)（\(1\leq{l}<{r}\leq{n}\)），将\(a_l\)变成\(1-a_l\)，将\(a_r\)变成\(1-a_r\)，\(l+1=r\)，则代价是\(x\)，否则代价是\(y\)，操作次数不限，求使两个串相同的最小代价，若无解输出-1
题解
设两个01串有\(cnt\)个位置不同，如果\(cnt\)为奇数，显然无解
如果\(cnt\)是偶数，以下进行分类讨论
-
\(x\geq{y}\)
特判一下\(cnt=2\)且这两个位置是相邻的情况，此时的答案为\(min(2*y,x)\)
否则，我们总可以选\(cnt/2\)组不相邻的位置（因为选相邻总是不优的），此时答案为\(cnt/2*y\)
-
\(x<y\)
处理出所有两个01串不同的位置，原问题等价于把这些位置分成\(cnt/2\)组，每组的策略如下：
设这两个位置是\(l\)和\(r\)，相邻的话显然直接操作，不相邻的话，直接操作或者移动某个位置，直到相邻后再操作
因此，最小代价为\(min(y,(r-l)*x)\)
我们在pos数组上考虑区间dp，考虑区间\([l,r]\)，我们可以证明dp只有三种情况：\(l,l+1\)同组，\(r,r-1\)同组，\(l,r\)同组
预处理区间长度为2的情况，只dp区间长度为偶数的区间，答案即为\(f[1][cnt]\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5007;
ll n,x,y,a[N],b[N],f[N][N],pos[N];
void read(ll &x){
char c=getchar();
x=0;
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
}
ll read(){
char c=getchar();
while(c!='0'&&c!='1'){
c=getchar();
}
return c-'0';
}
ll calc(ll l,ll r){
return min((r-l)*x,y);
}
void work(){
ll i,j,cnt=0;
read(n),read(x),read(y);
for(i=1;i<=n;++i){
a[i]=read();
}
for(i=1;i<=n;++i){
b[i]=read();
}
for(i=1;i<=n;++i){
if(a[i]!=b[i]){
pos[++cnt]=i;
}
}
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2&&pos[2]-pos[1]==1){
printf("%lld\n",min(2*y,x));
}
else{
printf("%lld\n",cnt/2*y);
}
}
else{
for(i=1;i<cnt;++i){
f[i][i+1]=calc(pos[i],pos[i+1]);
}
for(i=4;i<=cnt;i+=2){
for(j=1;j+i-1<=cnt;++j){
ll l=j,r=j+i-1;
f[l][r]=min(min(f[l+2][r]+calc(pos[l],pos[l+1]),f[l][r-2]+calc(pos[r-1],pos[r])),
f[l+1][r-1]+calc(pos[l],pos[r]));
}
}
printf("%lld\n",f[1][cnt]);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}