2022河南萌新联赛第（七）场：南阳理工学院 B 龍

B-龍_2022河南萌新联赛第（七）场：南阳理工学院 (nowcoder.com)

题意：

思路：

问全部变为1的最小花费为多少。

分析：不全为1则至少存在一段0区间，那么就必须要采取取反操作。假设有 sum 个0区间，存在三种方法：

1. 把所有0区间全翻转到一起，至少需要sum−1操作，再进行一次取反操作。
2. 对每个0区间直接取反。
3. 对区间进行两种操作，设翻转操作进行 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 
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;
}