好悬没想到,每次交换只可能有两种固定模式,一种是交换后最后统一 把0变1,另一种是把分散的0变成1.要想得出这个结论,需要先考虑较小的问题,逐步推到较大的问题上,类似贪心的策略
#include<bits/stdc++.h> using namespace std; string s; int a[300010]; int b[300010]; int tot; int main() { int n,x,y; scanf("%d%d%d",&n,&x,&y); cin>>s; for(int i=0;s[i];i++) { a[i+1]=s[i]-'0'; } a[0]=-1; for(int i=1;i<=n;i++) { if(a[i]!=a[i-1]) { b[++tot]=a[i]; } } int cnt=0; for(int i=1;i<=tot;i++) { if(b[i]==0) cnt++; } if(cnt==0) { printf("0\n"); return 0; } if(x>=y) { printf("%lld\n",1LL*cnt*y); } else { printf("%lld\n",1LL*y+1LL*(cnt-1)*x); } }