CF1107E Vasya and Binary String

Vasya 有一个长度为 $n$ 的字符串 $s$，该字符串只包含数字 $0$ 和 $1$。他还有一个长度为 $n$ 的数组 $a$。 Vasya 会不断进行如下操作，直到字符串变为空：选择一段连续且字符相同的子串，将其从字符串中删除，并将剩余部分拼接起来（剩余部分可以为空）。例如，如果他从字符串 111110 中删除子串 111，他将得到字符串 110。每当他删除长度为 $x$ 的子串时，他会获得 $a_x$ 分。 Vasya 想要让自己的总得分最大，请你帮助他实现这个目标。

第一行包含一个整数 $n$（$1 \le n \le 100$），表示字符串 $s$ 的长度。 第二行包含字符串 $s$，仅由数字 $0$ 和 $1$ 组成。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示删除长度为 $i$ 的子串可以获得的分数。

输出一个整数，表示 Vasya 能获得的最大总分。

在第一个样例中，最优的删除顺序为：1101001 $\rightarrow$ 111001 $\rightarrow$ 11101 $\rightarrow$ 1111 $\rightarrow$ $\varnothing$。 在第二个样例中，最优的删除顺序为：10101 $\rightarrow$ 1001 $\rightarrow$ 11 $\rightarrow$ $\varnothing$。 由 ChatGPT 4.1 翻译