题意:给你一个\(01\)串,需要将所有的\(1\)给炸掉,每次炸都可以将一整个\(1\)的联通块炸掉,每炸一次消耗\(a\),可以将\(0\)转化为\(1\),消耗\(b\),问将所有\(1\)都炸掉的最小花费.
题解:贪心,如果\(1\)存在,那么我们至少要炸一次,然后可以枚举统计两个连通块之间的\(0\)的个数,判断是将这些\(0\)变为\(1\)然后炸一次的花费小,还是炸掉\(2\)个连通块的花费小,思路就是这样,具体实现见代码.
-
代码:
int t;
int a,b;
string s; int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>a>>b;
cin>>s; int l=0,r=0;
int cnt0=0,cnt1=0;
int len=(int)s.size();
while(l<len && s[l]=='0') l++;
if(l<len) cnt1=1;
r=l;
while(r<len){
while(r<len && s[r]=='1') r++;
if(r==len) break;
l=r-1;
while(r<len && s[r]=='0') r++;
if(r==len) break;
if((r-l-1)*b<a) cnt0+=(r-l-1);
else cnt1++;
}
cout<<cnt0*b+cnt1*a<<'\n';
} return 0;
}