← 返回题目列表

Codeforces · 997/A

A. 转换为个

中文机器翻译题面 查看原题

你有一个字符串 $$$a_1, a_2, \dots, a_n$$$,由零和一组成。

让我们将连续元素序列 $$$a_i, a_{i + 1}, \ldots, a_j$$$ ($$$1\leq i\leq j\leq n$$$) 称为字符串 $$$a$$$ 的子字符串。

您可以多次应用以下操作:

- 选择字符串 $$$a$$$ 的某些子字符串(例如,您可以选择整个字符串)并将其反转,为此支付 $$$x$$$ 硬币(例如,«0101101» $$$\to$$$ «0111001»);
- 选择字符串 $$$a$$$ 的某个子字符串(例如,您可以选择整个字符串或仅选择一个符号)并将每个符号替换为相反的符号(零被 1 替换,1 被零替换),并为其支付 $$$y$$$ 硬币(例如,«0101101» $$$\to$$$ «0110001»)。

您可以按任意顺序应用这些操作。允许对同一子字符串多次应用操作。

要获得仅由 1 组成的字符串,您至少需要花费多少金币?

输入

输入的第一行包含整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$$$) - 字符串长度、第一个操作的成本(子串反转)和第二个操作的成本(反转子串的所有元素)子串)。

第二行包含长度为 $$$n$$$ 的字符串 $$$a$$$,由零和一组成。

输出

打印单个整数 - 获取仅由 1 组成的字符串所需的最小总操作成本。如果不需要执行任何操作,则打印$$$0$$$。

示例

输入 #1

5 1 10
01000

输出 #1

11

输入 #2

5 10 1
01000

输出 #2

2

输入 #3

7 2 3
1111111

输出 #3

0

注意

在第一个示例中,首先需要反转子字符串 $$$[1 \dots 2]$$$,然后需要反转子字符串 $$$[2 \dots 5]$$$。

然后字符串更改如下:

«01000» $$$\至$$$ «10000» $$$\至$$$ «11111»。

总运营成本为 $$$1 + 10 = 11$$$。

在第二个示例中,首先需要反转子字符串 $$$[1 \dots 1]$$$,然后需要反转子字符串 $$$[3 \dots 5]$$$。

然后字符串更改如下:

«01000» $$$\至$$$ «11000» $$$\至$$$ «11111»。

总成本为 $$$1 + 1 = 2$$$。

在第三个示例中,字符串已经仅由 1 组成,因此答案是 $$$0$$$。