UOJ Logo Universal Online Judge

UOJ

#725. 【JOISC2022】复制粘贴 3

附件下载 统计

JOI 公司是一家以“没啥用发明”而闻名的公司。最近,JOI 公司开发了一款名为“没啥用编辑器”的编辑器。

在这个编辑器中,可以执行如下几种操作来输入某个字符串,设 $X$ 为屏幕上的字符串,$Y$ 为剪切板中的字符串,初始均为空串:

  • 操作 A:输入字符 $c$,即将 $X$ 更新为 $X+c$。
  • 操作 B:选择所有字符并剪切,即将 $Y$ 更新为 $X$,并将 $X$ 置为空串。
  • 操作 C:将剪切板中的字符串粘贴到当前字符串末尾,即将 $X$ 更新为 $X+Y$。

对于字符串或字符 $x,y$,$x+y$ 表示将 $x$ 和 $y$ 顺次拼接得到的结果。使用一次操作 A,B,C 分别要花费 $A,B,C$ 单位时间。

你安装了“没啥用编辑器”,并想要尽可能快地输入一个长度为 $N$ 的字符串 $S$。

你需要计算出最少需要花费多少时间。

输入格式

第一行一个整数 $N$ 表示字符串长度。

第二行一个长度为 $N$ 的字符串 $S$ 表示要输入的字符串。

第三行一个整数 $A$ 表示操作 A 的代价。

第四行一个整数 $B$ 表示操作 B 的代价。

第五行一个整数 $C$ 表示操作 C 的代价。

输出格式

一行一个整数表示输入字符串 $S$ 最少要多少单位时间。

样例一

input

11
mississippi
10
5
2

output

88

explanation

以下是一组最优操作:

轮次 操作 解释 $X$ $Y$ 代价 总时间
- - - "" "" - $0$
$1$ 操作 A 输入字符 "s" "" $10$ $10$
$2$ 操作 B 全选并剪切 "" "s" $5$ $15$
$3$ 操作 C 在尾部粘贴 "s" "s" $2$ $17$
$4$ 操作 C 在尾部粘贴 "ss" "s" $2$ $19$
$5$ 操作 A 输入字符 "ssi" "s" $10$ $29$
$6$ 操作 B 全选并剪切 "" "ssi" $5$ $34$
$7$ 操作 A 输入字符 "m" "ssi" $10$ $44$
$8$ 操作 A 输入字符 "mi" "ssi" $10$ $54$
$9$ 操作 C 在尾部粘贴 "missi" "ssi" $2$ $56$
$10$ 操作 C 在尾部粘贴 "mississi" "ssi" $2$ $58$
$11$ 操作 A 输入字符 "mississip" "ssi" $10$ $68$
$12$ 操作 A 输入字符 "mississipp" "ssi" $10$ $78$
$13$ 操作 A 输入字符 "mississippi" "ssi" $10$ $88$

这组样例满足子任务 $3,4,5,6$ 的限制。

样例二

input

16
aaaaaaaaaaaaaaaa
1
1
1

output

9

explanation

一组最优策略如下:

轮次 操作 解释 $X$ $Y$ 代价 总时间
- - - "" "" - $0$
$1$ 操作 A 输入字符 "a" "" $1$ $1$
$2$ 操作 A 输入字符 "aa" "" $1$ $2$
$3$ 操作 A 输入字符 "aaa" "" $1$ $3$
$4$ 操作 A 输入字符 "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$ 的限制。

样例三

input

18
aababbbababbbaabbb
1000000000
100000
10000000

output

8060200000

explanation

这组样例满足子任务 $3,4,5,6$ 的限制。

数据范围与提示

  • $1\leq N\leq 2500$
  • $S$ 是一个长度为 $N$ 的小写字母串。
  • $1\leq A,B,C\leq 10^9$

Subtasks

  1. $\text{(1 points) }N=3$
  2. $\text{(5 points)}$ $S$ 只包含字符 a
  3. $\text{(14 points) }N\leq 30$
  4. $\text{(10 points) }N\leq 200$
  5. $\text{(32 points) }N\leq 1000$
  6. $\text{(38 points)}$ 无特殊限制。

时间限制:$\texttt{3s}$

空间限制:$\texttt{2GB}$