Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)

146 阅读 0 评论 97 点赞

我是靠谱客的博主辛勤溪流，这篇文章主要介绍Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)，现在分享给大家，希望可以做个参考。

题意：

给定两个01串s和t，每次操作可以选择 l 和 r ，并将s[l]和s[r]取反。若r==l+1，则代价为x，否则代价为y，问你把01串从s变到t的最少的代价

思路：

贪心，考虑贡献

首先判无解的情况，当需要修改的数的个数为奇数时显然无解

若x<y，则尽可能使用相邻的取反操作，若碰到相邻的则一定使用相邻取反操作，否则只能进行代价为y的操作

若x>y，则不管相邻还是不相邻，都用y操作就足以把所有需要修改的数都修改掉（因为需要修改的数的个数一定是偶数）

注意特判需要修改的数的个数只有2个时的条件，此时再对x和2*y进行讨论

如果x>2*y，则直接使用相邻的操作即可

否则，任选一个数，做两次代价为y的操作即可

Code：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int mxn=3e3+10;
#define int long long
string s,t;
int n,x,y,sum=0;
int ok[mxn];
void solve(){
s.clear(),t.clear();
sum=0;
memset(ok,0,sizeof(ok));
cin>>n>>x>>y;
cin>>s>>t;
s=" "+s;t=" "+t;
for(int i=1;i<=n;i++){
if(s[i]!=t[i]) ok[i]=1,sum++;
}
if(sum%2==1){
cout<<-1<<'n';
return;
}
if(sum==2){
if(x<2*y){
for(int i=2;i<=n;i++){
if(ok[i]&&ok[i-1]){
cout<<x<<'n';
return;
}
}
cout<<y<<'n';
return;
}else{
for(int i=2;i<=n;i++){
if(ok[i]&ok[i-1]){
cout<<y*2<<'n';
return;
}
}
cout<<y<<'n';
return;
}
}
int ans=0;
if(x<y){
for(int i=2;i<=n;i++){
if(ok[i]&&ok[i-1]){
ans+=x;
sum-=2;
ok[i]=ok[i-1]=0;
}
}
ans+=(sum/2)*y;
}else{
ans+=(sum/2)*y;
}
cout<<ans<<'n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}