题目大意
给定两个长度为 \(n\) 的二进制字符串 \(a\) 和 \(b\)，你可以进行若干次操作，对于每次操作：
- 选两个数 \(l\) 和 \(r\)，且 \(l<r\)，将 \(a_l\) 和 \(a_r\) 交换。
- 如果选取的 \(l\) 和 \(r\) 相邻，代价为 \(x\)，否则为 \(y\)。
保证 \(y≤x\)，求出最小代价使得 \(a=b\)，若不能使 \(a=b\)，输出 -1。
思路分析
贪心，很简单的一个分类讨论。
首先，根据 \(y≤x\)，要使得代价最小，尽量不交换相邻的。
记 \(a\) 和 \(b\) 不相同字符个数为 \(cnt\)，分为以下几种情况：
-
当 \(cnt\) 是奇数，无论怎么交换，都不能使 \(a=b\)，输出
-1。 -
否则，继续判断，特判若 \(cnt=0\)，即一开始 \(a=b\)，输出
0。 -
尽量让交换的两个数不相邻，所以若 \(cnt>2\)，则选择都不相邻的两个进行交换，进行 \(\frac{cnt}{2}\) 次不相邻交换，代价即为 \(\frac{cnt \cdot y}{2}\)。
-
还有一种，当 \(cnt=2\)，就需要判断是否相邻了：不相邻则输出 \(y\)；相邻，则考虑进行一次代价为 \(x\) 的交换，或两次代价为 \(y\) 的交换（另外找一个字符进行交换），求两种哪种最优，即 \(\min(x,2y)\)。
因为 \(y≤x≤10^9\)，交换次数越多，可能会爆 int，要开 long long。
最后记得加上换行。
代码：
/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
int num[3005];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
long long len,x,y,cnt=0;
string a,b;
cin>>len>>x>>y>>a>>b;
for(int i=0;i<len;i++)
{
if(a[i]!=b[i])
{
num[++cnt]=i;
}
}
if(cnt%2==1)
{
cout<<"-1\n";
}
else
{
if(cnt==0)
{
cout<<"0\n";
}
else if(cnt==2)
{
if(num[1]+1!=num[2])
{
cout<<y<<"\n";
}
else
{
cout<<min(x,2*y)<<"\n";
}
}
else
{
cout<<cnt/2*y<<"\n";
}
}
}
return 0;
}