P9523 [JOIST 2022] Copy and Paste 3 / Copy and Paste 3

JOISC2022 D2T1

JOI Company is a company famous for “useless inventions”. Recently, JOI Company developed an editor called the “Useless Editor”. In this editor, you can perform the following operations to input a string. Let $X$ be the string on the screen and $Y$ be the string in the clipboard. Initially, both are empty strings: - Operation A: Input a character $c$, i.e. update $X$ to $X+c$. - Operation B: Select all characters and cut, i.e. update $Y$ to $X$, and set $X$ to the empty string. - Operation C: Paste the string in the clipboard to the end of the current string, i.e. update $X$ to $X+Y$. For strings or characters $x,y$, $x+y$ means the result of concatenating $x$ and $y$ in order. Performing one operation A, B, C costs $A,B,C$ units of time respectively. You installed the “Useless Editor” and want to input a string $S$ of length $N$ as fast as possible. You need to compute the minimum total time required.

The first line contains an integer $N$, the length of the string. The second line contains a string $S$ of length $N$, the string to be typed. The third line contains an integer $A$, the cost of operation A. The fourth line contains an integer $B$, the cost of operation B. The fifth line contains an integer $C$, the cost of operation C.

Output one integer in one line, the minimum number of time units required to input the string $S$.

**[Sample Explanation #1]** One optimal sequence of operations is as follows: | Round | Operation | Explanation | $X$ | $Y$ | Cost | Total Time | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | - | - | - | `""` | `""` | - | $0$ | | $1$ | Operation A | Input a character | `"s"` | `""` | $10$ | $10$ | | $2$ | Operation B | Select all and cut | `""` | `"s"` | $5$ | $15$ | | $3$ | Operation C | Paste at the end | `"s"` | `"s"` | $2$ | $17$ | | $4$ | Operation C | Paste at the end | `"ss"` | `"s"` | $2$ | $19$ | | $5$ | Operation A | Input a character | `"ssi"` | `"s"` | $10$ | $29$ | | $6$ | Operation B | Select all and cut | `""` | `"ssi"` | $5$ | $34$ | | $7$ | Operation A | Input a character | `"m"` | `"ssi"` | $10$ | $44$ | | $8$ | Operation A | Input a character | `"mi"` | `"ssi"` | $10$ | $54$ | | $9$ | Operation C | Paste at the end | `"missi"` | `"ssi"` | $2$ | $56$ | | $10$ | Operation C | Paste at the end | `"mississi"` | `"ssi"` | $2$ | $58$ | | $11$ | Operation A | Input a character | `"mississip"` | `"ssi"` | $10$ | $68$ | | $12$ | Operation A | Input a character | `"mississipp"` | `"ssi"` | $10$ | $78$ | | $13$ | Operation A | Input a character | `"mississippi"` | `"ssi"` | $10$ | $88$ | This sample satisfies the constraints of subtasks $3,4,5,6$. **[Sample Explanation #2]** One optimal strategy is as follows: | Round | Operation | Explanation | $X$ | $Y$ | Cost | Total Time | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | - | - | - | `""` | `""` | - | $0$ | | $1$ | Operation A | Input a character | `"a"` | `""` | $1$ | $1$ | | $2$ | Operation A | Input a character | `"aa"` | `""` | $1$ | $2$ | | $3$ | Operation A | Input a character | `"aaa"` | `""` | $1$ | $3$ | | $4$ | Operation A | Input a character | `"aaaa"` | `""` | $1$ | $4$ | | $5$ | Operation B | Select all and cut | `""` | `"aaaa"` | $1$ | $5$ | | $6$ | Operation C | Paste at the end | `"aaaa"` | `"aaaa"` | $1$ | $6$ | | $7$ | Operation C | Paste at the end | `"aaaaaaaa"` | `"aaaa"` | $1$ | $7$ | | $8$ | Operation C | Paste at the end | `"aaaaaaaaaaaa"` | `"aaaa"` | $1$ | $8$ | | $9$ | Operation C | Paste at the end | `"aaaaaaaaaaaaaaaa"` | `"aaaa"` | $1$ | $9$ | This sample satisfies the constraints of subtasks $2,3,4,5,6$. **[Sample Explanation #3]** This sample satisfies the constraints of subtasks $3,4,5,6$. **[Constraints]** For all testdata, it holds that: - $1\leq N\leq 2500$. - $S$ is a lowercase letter string of length $N$. - $1\leq A,B,C\leq 10^9$. The additional constraints and scores for each subtask are shown in the table below: | Subtask ID | Additional Constraints | Score | |:-:|:-:|:-:| | $1$ | $N=3$ | $1$ | | $2$ | $S$ contains only the character $\texttt a$ | $5$ | | $3$ | $N\le 30$ | $14$ | | $4$ | $N\le 200$ | $10$ | | $5$ | $N \le 1000$ | $32$ | | $6$ | No additional constraints | $38$ | Translated by ChatGPT 5