CF1120C Compress String

给定一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。你需要用最少的金币数对其进行压缩。 压缩字符串的方法是，将 $s$ 表示为若干个非空字符串的连接：$s = t_{1} t_{2} \ldots t_{k}$。对于第 $i$ 个字符串 $t_{i}$，有两种编码方式： - 如果 $|t_{i}| = 1$，即当前字符串仅包含一个字符，则编码需要花费 $a$ 个金币； - 如果 $t_{i}$ 是 $t_{1} t_{2} \ldots t_{i-1}$ 的子串，则编码需要花费 $b$ 个金币。 字符串 $x$ 是字符串 $y$ 的子串，表示 $x$ 可以通过删除 $y$ 开头和结尾的若干（可能为零或全部）字符得到。 你的任务是计算压缩给定字符串 $s$ 所需的最小金币数。

第一行包含三个正整数，空格分隔：$n$、$a$ 和 $b$（$1 \leq n, a, b \leq 5000$），分别表示字符串的长度、压缩单字符的花费和压缩已出现过的子串的花费。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

输出一个整数，表示压缩字符串 $s$ 所需的最小金币数。

在第一个样例中，可以设 $t_{1} = $ 'a'，$t_{2} = $ 'b'，$t_{3} = $ 'a'，共需 $3 + 3 + 1 = 7$ 个金币，因为 $t_{3}$ 是 $t_{1}t_{2}$ 的子串。 在第二个样例中，只需将每个字符单独压缩即可。 在第三个样例中，可以设 $t_{1} = t_{2} = $ 'a'，$t_{3} = $ 'aa'，共需 $10 + 1 + 1 = 12$ 个金币，因为 $t_{2}$ 是 $t_{1}$ 的子串，$t_{3}$ 是 $t_{1}t_{2}$ 的子串。 由 ChatGPT 4.1 翻译