CF1733D
给定两个 \(01\) 序列，你每次操作可以同时对同一个序列的两个位置的数取反，如果这两个位置相邻则代价为 \(x\)，反之为 \(y\)，问让两个序列相等的最小代价，不可能达成则输出 \(-1\)
新建一个 \(01\) 序列，预处理不同的位置为 \(1\)，相同的为 \(0\)，问题即为将数组归 \(0\)，显然1的数量为奇数一定不可能达成，为偶数一定可以达成
因为不相邻的操作比相邻的操作更灵活，所以如果 \(y\leq x\) 的话，对于几乎任意序列我们都可以全用 \(y\) 的代价进行修改，再对整个序列仅有两个相邻的 \(1\) 单独讨论
如果 \(x\leq y\)，那么不相邻的两个位置可以用若干相邻的修改实现，而最优情况下一个地方修改过便不可能重复修改，所以可以 \(dp\)，每次可以选择和最近的那一个用 \(x\) 代价修改，也可以和之前没有被修改的那个位置用 \(y\) 修改，复杂度 \(O(n)\)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))
using namespace std;
const int N = 2e6 + 10;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int n, x, y, a[N];
long long f[N];
char s[N], t[N];
int main() {
int T = read();
while (T--) {
n = read(); x = read(); y = read();
cin >> (s + 1) >> (t + 1);
int cnt = 0;
for (int i = 1; i <= n; i++) if (s[i] ^ t[i]) a[++cnt] = i;
n = cnt;
if (n & 1) {puts("-1"); continue;}
if (x >= y) {
if (n == 2) printf("%d\n", a[2] - a[1] == 1 ? min(x, y << 1) : y);
else printf("%lld\n", 1ll * (n >> 1) * y);
continue;
}
f[1] = 0; f[2] = min(1ll * y, 1ll * (a[2] - a[1]) * x);
for (int i = 3; i <= n; i++) {
f[i] = min(f[i - 2] + 1ll * (a[i] - a[i - 1]) * x, f[i - 1] + (i % 2 == 0) * y);
}
printf("%lld\n", f[n]);
}
return 0;
}