题目描述

输入 n(1≤n≤3e5) x(0≤x≤1e9) y(0≤y≤1e9) 和长为 n 的 01 字符串 s。

你可以执行任意次操作，每次选择其中一种操作执行。
1. 花费 x，reverse s 的一个子串，例如 1110 -> 0111。
2. 花费 y，flip s 的一个子串，例如 1110 -> 0001。

目标：使 s 中只有 1。
输出最少花费。

样例

输入样例1

5 1 10
01000

输出样例1

11

输入样例2

5 10 1
01000

输出样例2

2

输入样例3

7 2 3
1111111

输出样例3

0

(贪心) $O(n)$

题目中需要将所有的0变成1，贪心的点在于我们如果要合并0，一定会合并两堆连续最多的0，例如10001100，我们要是合并0的话一定要将前面的三个0和后面的两个0合并，而不能取前面的部分0和后面的部分0合并。可以证明这样最优，如果我们不这样合并的话，那么还会有剩余的零需要我们去合并，操作数一定会变大，所以每次合并要一段连续的0。
第二个点在于我们发现，合并任意两段连续的0操作数是一样的，所以我们只需要每次合并相距最近的一段0就好。
那么我们就可以暴力枚举，枚举i从开头到结尾，i之前所有的0要合并成一段后在执行取反操作，i后面的每一段0要单独执行取反操作，每次更新答案的最小值。这样可以考虑到所有的情况。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 3e5+10, M = N * 2, INF = 0x3f3f3f3f;

char s[N];
int n, x, y;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>x>>y;
    cin>>s+1;

    LL res = 1e18;
    int last = 0;
    int cnt = 0;
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<=n && s[i]==s[j]) j++;
        s[++cnt]=s[i];
        i = j - 1;
    }
    int sum = 0;
    for(int i=1;i<=cnt;i++) sum += s[i] == '0';
    for(int i=1;i<=cnt;i++){
        if(s[i]=='0'){
            LL tmp = (LL)(sum - last - 1) * y + (LL)last * x + y;
            res = min(res, tmp);
            last++;
        }
    }

    if(res>=1e18/2) cout<<0<<endl;
    else cout<<res<<endl;

    return 0;
}