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：

#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;
}

最后

以上就是辛勤溪流为你收集整理的Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)的全部内容，希望文章能够帮你解决Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)所遇到的程序开发问题。

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