B. Saving the City

题目传送门

B. Saving the City

题目大意

给你一个01字符串s，消除其中连续的1耗费a，将一个0变为1耗费b，求将整个字符串s全部变成0所消耗的最小值

思路

取将不相连的两段相连与否的最小值即可，即为
第一个连续的1直接耗费a，后面记录到下一段的1的距离（即为中间0的个数），然后$min(sum\ast b,a)$即可

AC Code

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
#include
#include
#include
#include
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int a, b, ans;
string s;
void solve(){cin>>a>>b;cin>>s;ans=0;int flag=0, sum=0;for(int i=0; i<s.length(); i++){if(s[i]=='1'){if(!flag) flag=1, ans=a;else      ans+=min(a,sum*b);sum=0;}if(s[i]=='0') sum++;}cout<<ans<<endl;return ;
}signed main(){int T;cin>>T;while(T--) solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！