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;
}
标签:修改,int,相邻,CF1733D,序列,include
From: https://www.cnblogs.com/zrzring/p/CF1733D.html