CF1550B Maximum Cost Deletion

给定一个长度为 $n$ 的仅由字符 $0$ 和 $1$ 组成的字符串 $s$。 你需要不断进行如下操作直到字符串变为空：选择一段连续且字符相同的子串，将其从字符串中删除，并将剩余的两部分（任意一部分可以为空）按原顺序拼接。例如，如果你从字符串 111110 中删除子串 111，你将得到字符串 110。当你删除长度为 $l$ 的子串时，你可以获得 $a \cdot l + b$ 分。 你的任务是计算，在必须将给定字符串删空的前提下，你最多能获得多少分。

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$a$ 和 $b$（$1 \le n \le 100; -100 \le a, b \le 100$），分别表示字符串 $s$ 的长度以及参数 $a$ 和 $b$。 每个测试用例的第二行包含一个仅由字符 $0$ 和 $1$ 组成的字符串 $s$。

对于每个测试用例，输出一个整数，表示你最多能获得的分数。

在第一个样例中，直接删除整个字符串即可获得 $2 \cdot 3 + 0 = 6$ 分。 在第二个样例中，如果每次只删除一个字符，则每次可获得 $(-2) \cdot 1 + 5 = 3$ 分，总共可以获得 $15$ 分。 在第三个样例中，可以先从字符串 100111 中删除子串 00，获得 $1 \cdot 2 + (-4) = -2$ 分，剩下字符串 1111，全部删除可获得 $1 \cdot 4 + (-4) = 0$ 分。总共进行了两次操作，获得 $-2$ 分。 由 ChatGPT 4.1 翻译