D1. Zero-One (Easy Version) codeforces 1733D1

Problem - 1733D1 - Codeforces

题目大意：有两个长度为n的仅包含0和1的字符串s1,s2，如果对于同一个位置i，s1[i]!=s2[i],可以选择另一个位置j，将这两个位置上的数取反，如果i和j是相邻的，花费是x，否则花费为y,问要使两个字符串相同，最小花费是多少

5<=n<=3000,1<=y<=x<=1e9

思路：因为每次操作都是两个位置同时取反，所以我们先统计满足s1[i]!=s2[i]的i的数量cnt，如果为奇数，则无法使两个字符串相同,然后只要cnt!=2,那么我们一定可以对每个不匹配的位置都找到一个不相邻的不匹配的位置，两个位置同时取反，消耗为y，最小的花费为cnt/2*y，当cnt=2时，且如果两个不匹配的位置相邻，那么我们可以将这两个位置取反，或者找到另一个位置，使这两个不匹配的位置分别与这个位置取反，最小费用为2y和x的最小值，如果两个不匹配的位置不相邻，最小费用为y

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;//注意数据范围
int main()
{
int t;
cin >> t;
while (t--)
{
ll n, x, y;
scanf_s("%lld%lld%lld", &n, &x, &y);
string s1, s2;
cin >> s1 >> s2;
ll cnt = 0, cnt2 = 0;
for (int i = 0; i < n; i++)
{
if (s1[i] != s2[i])
{
cnt++;//记录不匹配的位置的数量
}
}
for (int i = 0; i < n; i++)
{
if (i != 0 && s1[i] != s2[i] && s1[i - 1] != s2[i - 1])
{
cnt2++;//记录相邻的不匹配的位置的组数
i++;
}
}
if (cnt & 1)
{//只有奇数个不匹配，直接输出-1
printf("-1n");
continue;
}
ll ans = 0;
if (cnt == 2 && cnt2 == 1)
{//不匹配的有两个且相邻
ans = min(x,2 * y);
}
else
{
ans = cnt/2 * y;
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是俊逸香水为你收集整理的D1. Zero-One (Easy Version) codeforces 1733D1的全部内容，希望文章能够帮你解决D1. Zero-One (Easy Version) codeforces 1733D1所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。