题目描述
输入 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;
}