P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3

JOISC2022 D2T1

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$ 最少要多少单位时间。

**【样例解释 #1】** 以下是一组最优操作： | 轮次 | 操作 | 解释 | $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$ 的限制。 **【样例解释 #2】** 一组最优策略如下： | 轮次 | 操作 | 解释 | $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$ 的限制。 **【样例解释 #3】** 这组样例满足子任务 $3,4,5,6$ 的限制。 **【数据范围】** 对于所有数据，满足： - $1\leq N\leq 2500$ - $S$ 是一个长度为 $N$ 的小写字母串。 - $1\leq A,B,C\leq 10^9$ 详细子任务附加限制及分值如下表所示： |子任务编号|附加限制|分数| |:-:|:-:|:-:| |$1$|$N=3$|$1$| |$2$|$S$ 只包含字符 $\texttt a$|$5$| |$3$|$N\le 30$|$14$| |$4$|$N\le 200$|$10$| |$5$|$N \le 1000$|$32$| |$6$|无附加限制|$38$|