2022河南萌新联赛第（七）场：南阳理工学院 B 龍
B-龍_2022河南萌新联赛第（七）场：南阳理工学院 (nowcoder.com)
题意：
思路：
问全部变为1的最小花费为多少。
分析：不全为1则至少存在一段0区间，那么就必须要采取取反操作。假设有 sum 个0区间，存在三种方法：
- 把所有0区间全翻转到一起，至少需要sum−1操作，再进行一次取反操作。
- 对每个0区间直接取反。
- 对区间进行两种操作，设翻转操作进行 i 次，取反操作进行 j 次操作，i+j==sum
因为每翻转一次就会消去一个0区间，就会少取反一次区间，所以上述等式成立。
再进一步分析，每种方法都需要sum次操作，其中一定存在一次取反操作，其余要么（）（sum−1）∗a次翻转操作，要么（）（sum−1）∗b次取反操作, 要么i∗a+j∗b次混合操作。 要根据和a和b大小决定操作，并且3操作一定不会是最优操作或者可以被其他两种操作取代（a等于b时）。
最后答案合并就是 b+min(a,b)∗(k−1)
#include <bits/stdc++.h>
using namespace std;
const int mxn=3e5+10;
#define int long long
int n,a,b,x,ans=0,cnt=0;
char s[mxn];
void solve(){
cnt=0;
scanf("%lld%lld%lld%lld",&n,&a,&b,&x);
scanf("%s",s+1);
for(int i=1;i<=n-1;i++){
if(s[i]=='0'&&s[i+1]=='1') cnt++;
}
if(s[n]=='0') cnt++;
ans=x;
if(cnt) ans=x-min(a,b)*(cnt-1)-b;
if(ans>=0){
puts("Yes");
printf("%lld\n",ans);
}else puts("No");
}
signed main(){
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}