/
実行時間制限: 3 sec / メモリ制限: 2048 MiB
Score: 100 points
Problem Statement
JOI, Ltd. is a company known for their “just odd inventions.” Recently, JOI, Ltd. developed a text editor called “Just Odd Editor.”
Using this text editor, we can input a string of characters by performing the following operations several times. Let X be the string displayed on the screen of the text editor. Let Y be the string saved in the clipboard. In the beginning, both of X and Y are the empty string.
- Operation A : We add one character in the end of the string. Namely, we choose a character c, and update X to be X + c.
- Operation B : We select all the characters and cut them. Namely, we update Y to be X. After that, we set X to be the empty string.
- Operation C : We paste the string from the clipboard at the end of the string. Namely, we update X to be X + Y.
Here, for characters or strings x, y, the string x + y means the string obtained by connecting x with y in this order. Performing an operation takes time. If we perform the operation A, B, C once, it takes A, B,C unit time, respectively.
You installed Just Odd Editor. You want to input a string S of length N as soon as possible. Performing operations, you want to make the string on the display be S as soon as possible.
Write a program which, given the length N, the string S, and the amount of unit time needed to perform an operation, calculates the least amount of time needed to input the string S.
Input
Read the following data from the standard input.
N S A B C
Output
Write one line to the standard output. The output should contain the least amount of time needed to input the string S.
Constraints
- 1 \le N \le 2\,500.
- S is a string of length N. Each character of S is a lower-case alphabet (’
a’ - ’z’). - 1 \le A \le 1\,000\,000\,000 (= 10^{9}).
- 1 \le B \le 1\,000\,000\,000 (= 10^{9}).
- 1 \le C \le 1\,000\,000\,000 (= 10^{9}).
- N, A, B,C are integers.
Subtasks
- (7 points) N = 3.
- (18 points) Every character of S is ’
a’. - (18 points) N \le 30.
- (11 points) N \le 200.
- (22 points) N \le 1\,000.
- (24 points) No additional constraints.
Sample Input 1
11 mississippi 10 5 2
Sample Output 1
88
By performing the following operations, we can input mississippi by 88 unit time. Since it is the least amount of time needed to input mississippi, output 88.
| Order | Operation | Explanation | X | Y | Time | Total Time |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | 0 |
| 1 | Operation A | Add a character in end | "s" |
"" |
10 | 10 |
| 2 | Operation B | Select all & Cut | "" |
"s" |
5 | 15 |
| 3 | Operation C | Paste at end | "s" |
"s" |
2 | 17 |
| 4 | Operation C | Paste at end | "ss" |
"s" |
2 | 19 |
| 5 | Operation A | Add a character in end | "ssi" |
"s" |
10 | 29 |
| 6 | Operation B | Select all & Cut | "" |
"ssi" |
5 | 34 |
| 7 | Operation A | Add a character in end | "m" |
"ssi" |
10 | 44 |
| 8 | Operation A | Add a character in end | "mi" |
"ssi" |
10 | 54 |
| 9 | Operation C | Paste at end | "missi" |
"ssi" |
2 | 56 |
| 10 | Operation C | Paste at end | "mississi" |
"ssi" |
2 | 58 |
| 11 | Operation A | Add a character in end | "mississip" |
"ssi" |
10 | 68 |
| 12 | Operation A | Add a character in end | "mississipp" |
"ssi" |
10 | 78 |
| 13 | Operation A | Add a character in end | "mississippi" |
"ssi" |
10 | 88 |
This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.
Sample Input 2
16 aaaaaaaaaaaaaaaa 1 1 1
Sample Output 2
9
By performing the following operations, we can input aaaaaaaaaaaaaaaa by 9 unit time. Since it is the least amount of time needed to input aaaaaaaaaaaaaaaa, output 9.
| Order | Operation | Explanation | X | Y | Time | Total Time |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | 0 |
| 1 | Operation A | Add a character in end | "a" |
"" |
1 | 1 |
| 2 | Operation A | Add a character in end | "aa" |
"" |
1 | 2 |
| 3 | Operation A | Add a character in end | "aaa" |
"" |
1 | 3 |
| 4 | Operation A | Add a character in end | "aaaa" |
"" |
1 | 4 |
| 5 | Operation B | Select all & Cut | "" |
"aaaa" |
1 | 5 |
| 6 | Operation C | Paste at end | "aaaa" |
"aaaa" |
1 | 6 |
| 7 | Operation C | Paste at end | "aaaaaaaa" |
"aaaa" |
1 | 7 |
| 8 | Operation C | Paste at end | "aaaaaaaaaaaa" |
"aaaa" |
1 | 8 |
| 9 | Operation C | Paste at end | "aaaaaaaaaaaaaaaa" |
"aaaa" |
1 | 9 |
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.
Sample Input 3
18 aababbbababbbaabbb 1000000000 100000 10000000
Sample Output 3
8060200000
This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.
配点 : 100 点
問題文
ただ奇妙な発明で知られる JOI 社は,最近 Just Odd Editor というテキストエディタを開発した.
このテキストエディタでは,以下の操作のいずれかを繰り返すことで,文字列を入力することができる.説明の都合上,現在テキストエディタの画面に表示されている文字列を X,クリップボードに保存されている文字列を Y とする.最初の時点では,X と Y はどちらも空文字列である.
- 操作 A:末尾に 1 文字入力する.すなわち,ある文字 c を決めて,X を X + c に更新する.
- 操作 B:全選択して切り取りする.すなわち,Y を X に更新した後,X を空文字列に更新する.
- 操作 C:末尾に貼り付けする.すなわち,X を X + Y に更新する.
ただし,文字または文字列 x, y に対し,x + y は「x, y をこの順で連結した文字列」を表すものとする.また,各操作には一定の時間がかかり,具体的には操作 A, B, C を 1 回行うのにそれぞれ A, B,C 単位時間かかる.
あなたは Just Odd Editor をインストールしたので,できるだけ早く長さ N の文字列 S を入力したいと思っている.すなわち,操作手順を工夫することで,できるだけ短い時間で画面に表示されている文字列を S に一致させたい.
文字列の長さ N,文字列 S および各操作に必要な時間が与えられるので,文字列 S を入力するのに必要な時間の最小値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N S A B C
出力
標準出力に,文字列 S を入力するのに必要な時間の最小値を 1 行で出力せよ.
制約
- 1 \leqq N \leqq 2\,500.
- S は英小文字 (’
a’ - ’z’) からなる長さ N の文字列である. - 1 \leqq A \leqq 1\,000\,000\,000 (= 10^{9}).
- 1 \leqq B \leqq 1\,000\,000\,000 (= 10^{9}).
- 1 \leqq C \leqq 1\,000\,000\,000 (= 10^{9}).
- N, A, B,C は整数である.
小課題
- (7 点) N = 3.
- (18 点) S のすべての文字は ’
a’ である. - (18 点) N \leqq 30.
- (11 点) N \leqq 200.
- (22 点) N \leqq 1\,000.
- (24 点) 追加の制約はない.
入力例 1
11 mississippi 10 5 2
出力例 1
88
以下の表のように操作すると,88 単位時間で mississippi を入力できる.これより少ない時間で mississippi を入力することはできないので,88 を出力する.
| 順番 | 種類 | 操作内容 | X | Y | 時間 | 累計時間 |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | 0 |
| 1 | 操作 A | 末尾に 1 文字入力 | "s" |
"" |
10 | 10 |
| 2 | 操作 B | 全選択して切り取り | "" |
"s" |
5 | 15 |
| 3 | 操作 C | 末尾に貼り付け | "s" |
"s" |
2 | 17 |
| 4 | 操作 C | 末尾に貼り付け | "ss" |
"s" |
2 | 19 |
| 5 | 操作 A | 末尾に 1 文字入力 | "ssi" |
"s" |
10 | 29 |
| 6 | 操作 B | 全選択して切り取り | "" |
"ssi" |
5 | 34 |
| 7 | 操作 A | 末尾に 1 文字入力 | "m" |
"ssi" |
10 | 44 |
| 8 | 操作 A | 末尾に 1 文字入力 | "mi" |
"ssi" |
10 | 54 |
| 9 | 操作 C | 末尾に貼り付け | "missi" |
"ssi" |
2 | 56 |
| 10 | 操作 C | 末尾に貼り付け | "mississi" |
"ssi" |
2 | 58 |
| 11 | 操作 A | 末尾に 1 文字入力 | "mississip" |
"ssi" |
10 | 68 |
| 12 | 操作 A | 末尾に 1 文字入力 | "mississipp" |
"ssi" |
10 | 78 |
| 13 | 操作 A | 末尾に 1 文字入力 | "mississippi" |
"ssi" |
10 | 88 |
この入力例は小課題 3, 4, 5, 6 の制約を満たす.
入力例 2
16 aaaaaaaaaaaaaaaa 1 1 1
出力例 2
9
以下の表のように操作すると,9 単位時間で aaaaaaaaaaaaaaaa を入力できる.これより少ない時間で aaaaaaaaaaaaaaaa を入力することはできないので,9 を出力する.
| 順番 | 種類 | 操作内容 | X | Y | 時間 | 累計時間 |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | 0 |
| 1 | 操作 A | 末尾に 1 文字入力 | "a" |
"" |
1 | 1 |
| 2 | 操作 A | 末尾に 1 文字入力 | "aa" |
"" |
1 | 2 |
| 3 | 操作 A | 末尾に 1 文字入力 | "aaa" |
"" |
1 | 3 |
| 4 | 操作 A | 末尾に 1 文字入力 | "aaaa" |
"" |
1 | 4 |
| 5 | 操作 B | 全選択して切り取り | "" |
"aaaa" |
1 | 5 |
| 6 | 操作 C | 末尾に貼り付け | "aaaa" |
"aaaa" |
1 | 6 |
| 7 | 操作 C | 末尾に貼り付け | "aaaaaaaa" |
"aaaa" |
1 | 7 |
| 8 | 操作 C | 末尾に貼り付け | "aaaaaaaaaaaa" |
"aaaa" |
1 | 8 |
| 9 | 操作 C | 末尾に貼り付け | "aaaaaaaaaaaaaaaa" |
"aaaa" |
1 | 9 |
この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.
入力例 3
18 aababbbababbbaabbb 1000000000 100000 10000000
出力例 3
8060200000
この入力例は小課題 3, 4, 5, 6 の制約を満たす.