C. Convert to Ones

2진수 a가 주어졌을 때 두가지 연산을 할 수 있다.

1. i~j 구간을 reverse

2. i~j 구간을 toggle

둘다 범위에 상관없이 한번의 연산으로 취급하며 1번 연산에 x, 2번 연산에 y만큼의 cost가 소모된다.

a를 모두 1로 만드는데 필요한 연산의 최소 횟수를 물어보는 문제다.

2진수의 형태를 보면 연속된 1의 덩어리와 연속된 0의 덩어리가 교차로 나타나는 형식이다.

000111100 같은 형태가 있을 때 이걸 모두 1로 만들기 위해서 할 수 있는 연산은

1. 1~7까지를 reverse하고 5~9까지 toggle한다.

2. 1~3까지 toggle, 8~9까지 toggle

이런 방식이다. 저 0,1 덩어리의 개수를 좀 더 늘려보자

0110100101 을 살펴보면

1.

reverse(1,3) -> 1100100101

reverse(3,5) -> 1110000101

reverse(4,8) -> 1111000001

toggle(5,9) -> 1111111111

2. 

reverse(1,3) -> 1100100101

reverse(3,5) -> 1110000101

toggle(4,7) -> 1111111101

toggle(9,9) -> 1111111111

...

이런방식으로 0의 덩어리를 하나로 뭉치는 과정에서 reverse 하나가 toggle 하나로 치환할 수 있는 방식이다.

즉 (cnt(chunk_of_zero) - 1)*x + y 부터 y*cnt(chunk_of_zero) 에서 정답이 나오는데 이건 

x>y인 경우에는 무조건 y*cnt가 답이 되고

y>x인 경우에는 무조건 (cnt-1)*x + y가 답이 되는걸 알 수 있다.

x==y인 경우에는 항상 같은값이 나오므로 고려할 필요가 없다.

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, x, y, cnt;
char s[300001];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> x >> y;
	cin >> s + 1;
	s[0] = '1';
	for (int i = 1; i <= n; ++i) 
		if (s[i] == '0' && s[i - 1] == '1')
			cnt++;
	if (!cnt)
		cout << "0";
	else 
		cout << min((cnt - 1)*x + y, cnt*y);
	return 0;
}