CF1443B Saving the City（思维）

给你一串01字符串，你可以花费a引爆一串连续的1，或者花费b让一个0变成1。问引爆这串字符串的所有1需要多少花费。

假设这串字符的1的联通块个数有num个，则他们之间0的联通块为num-1个。

若a<=b则ans为num*a，因为填补中间零加上引爆一次的花费至少为（num-1）b+a，直接引爆的花费为numa，因为a<=b故后者小。

若a>b，我们则处理出每两个1直接的0的个数，从小往大遍历，设当前0的个数为x，若xb+a<2a，则填补这些0。

故我们计算a的贡献次数和b的贡献次数，a原本贡献次数为num，每次填补都会贡献x次b，使a减少一次贡献，因为连着一起引爆了。

#include<iostream>#include<string.h>#include<algorithm>usingnamespacestd;constintmaxn=1e5+5;typedeflonglongll;intt,a,b,num1,len,flag;chars[maxn];intnum[maxn];ll ans;intmain(){cin>>t;while(t--){cin>>a>>b;cin>>s+1;num1=0;len=strlen(s+1);flag=1;ans=0;for(inti=1;i<=len;i++){if(s[i]=='1'&&flag){num1++;flag=0;}if(s[i]=='0'){flag=1;}}if(a<=b){cout<<num1*a<<'\n';continue;}intk=0,now=0;flag=0;for(inti=1;i<=len;i++){if(s[i]=='0'&&flag){now++;}if(s[i]=='1'&&now){num[++k]=now;now=0;}if(s[i]=='1')flag=1;}sort(num+1,num+1+k);intcnt=0;for(inti=1;i<=k;i++){if(num[i]*b+a<2*a){ans+=num[i];cnt++;}elsebreak;}ans=ans*b+(num1-cnt)*a;cout<<ans<<'\n';}}/* 100 1 1 00110001100101 */