103033: [Atcoder]ABC303 D - Shift vs. CapsLock
Description
Score : $400$ points
Problem Statement
Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.
You can do the following three actions any number of times in any order:
- Spend $X$ milliseconds to press only the 'a' key. If the light on the Caps Lock key is off,
a
is appended to the string on the screen; if it is on,A
is. - Spend $Y$ milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off,
A
is appended to the string on the screen; if it is on,a
is. - Spend $Z$ milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.
Given a string $S$ consisting of A
and a
, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to $S$.
Constraints
- $1 \leq X,Y,Z \leq 10^9$
- $X$, $Y$, and $Z$ are integers.
- $1 \leq |S| \leq 3 \times 10^5$
- $S$ is a string consisting of
A
anda
.
Input
The input is given from Standard Input in the following format:
$X$ $Y$ $Z$ $S$
Output
Print the answer.
Sample Input 1
1 3 3 AAaA
Sample Output 1
9
The following sequence of actions makes the string on the screen equal to AAaA
in $9$ milliseconds, which is the shortest possible.
- Spend $Z(=3)$ milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
- Spend $X(=1)$ milliseconds to press the 'a' key.
A
is appended to the string on the screen. - Spend $X(=1)$ milliseconds to press the 'a' key.
A
is appended to the string on the screen. - Spend $Y(=3)$ milliseconds to press the Shift key and 'a' key simultaneously.
a
is appended to the string on the screen. - Spend $X(=1)$ milliseconds to press the 'a' key.
A
is appended to the string on the screen.
Sample Input 2
1 1 100 aAaAaA
Sample Output 2
6
Sample Input 3
1 2 4 aaAaAaaAAAAaAaaAaAAaaaAAAAA
Sample Output 3
40
Input
题意翻译
Syx 是一个码农,但她的键盘不太一样,她的键盘仅由大小写的 `a`,`Shift`,`Caps lock` 组成。 如果 Syx 按下 `a` 键,则会打出 `a`,并耗费 $x$ 的时间。 如果她按下 `Shift + a` 键,则会打出大写的 `A`(若开启 `Caps lock` 则是 `a`),耗费 $y$ 的时间。 如果按下 `Caps lock`,则会开启/关闭大写锁定,耗费 $z$ 的时间。 现在她想打出一个字符串 $s$,请问最少耗时是多少。 by [Saint_ying_xtf](https://www.luogu.com.cn/user/852144)。Output
问题描述
你的电脑有一个键盘,有三个键:'a' 键,Shift 键和 Caps Lock 键。Caps Lock 键上有一个灯。起初,Caps Lock 键上的灯是关闭的,屏幕上显示一个空字符串。
你可以以任意顺序、任意次数执行以下三个操作:
- 花费 $X$ 毫秒按下 'a' 键。如果 Caps Lock 键上的灯关闭,
a
会被添加到屏幕上的字符串;如果灯亮着,则添加A
。 - 花费 $Y$ 毫秒同时按下 'a' 键和 Shift 键。如果 Caps Lock 键上的灯关闭,
A
会被添加到屏幕上的字符串;如果灯亮着,则添加a
。 - 花费 $Z$ 毫秒按下 Caps Lock 键。如果 Caps Lock 键上的灯关闭,它会打开;如果灯亮着,它会关闭。
给定一个由A
和a
组成的字符串 $S$,确定至少需要花费多少毫秒才能使屏幕上的字符串等于 $S$。
约束
- $1 \leq X,Y,Z \leq 10^9$
- $X$,$Y$ 和 $Z$ 是整数。
- $1 \leq |S| \leq 3 \times 10^5$
- $S$ 是由
A
和a
组成的字符串。
输入
输入从标准输入给出,格式如下:
$X$ $Y$ $Z$ $S$
输出
打印答案。
样例输入 1
1 3 3 AAaA
样例输出 1
9
以下操作序列在 $9$ 毫秒内使屏幕上的字符串等于 AAaA
,这是最短可能的时间。
- 花费 $Z(=3)$ 毫秒按下 CapsLock 键。Caps Lock 键上的灯打开。
- 花费 $X(=1)$ 毫秒按下 'a' 键。
A
被添加到屏幕上的字符串。 - 花费 $X(=1)$ 毫秒按下 'a' 键。
A
被添加到屏幕上的字符串。 - 花费 $Y(=3)$ 毫秒同时按下 Shift 键和 'a' 键。
a
被添加到屏幕上的字符串。 - 花费 $X(=1)$ 毫秒按下 'a' 键。
A
被添加到屏幕上的字符串。
样例输入 2
1 1 100 aAaAaA
样例输出 2
6
样例输入 3
1 2 4 aaAaAaaAAAAaAaaAaAAaaaAAAAA
样例输出 3
40