CF1621F Strange Instructions

Dasha 有 $10^{100}$ 个硬币。最近，她发现了一个长度为 $n$ 的二进制字符串 $s$，并且可以对该字符串进行如下操作（每种操作可以执行任意多次）： 1. 将 $s$ 中的子串 $00$ 替换为 $0$，并获得 $a$ 个硬币。 2. 将 $s$ 中的子串 $11$ 替换为 $1$，并获得 $b$ 个硬币。 3. 从 $s$ 的任意位置移除一个 $0$，并支付 $c$ 个硬币。 在进行这些操作时，Dasha 需要遵守以下规则： - 不允许连续执行两次奇偶性相同的操作。操作按照上面给出的顺序编号为 $1$ 到 $3$。 请你计算，在遵守上述规则的前提下，Dasha 能获得的最大利润是多少。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含四个整数 $n$、$a$、$b$、$c$（$1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9$）。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个答案。

在第一个测试用例中，一种最优的操作序列为 $01101 \rightarrow 0101 \rightarrow 011 \rightarrow 01$。该操作序列依次使用了操作 $2$、$3$ 和 $2$，满足所有规则，总利润为 $3$。可以证明无法获得更高的利润，因此答案为 $3$。 在第二个测试用例中，一种最优的操作序列为 $110001 \rightarrow 11001 \rightarrow 1001 \rightarrow 101$。 在第三个测试用例中，一种最优的操作序列为 $011110 \rightarrow 01110 \rightarrow 1110 \rightarrow 110 \rightarrow 11 \rightarrow 1$。 由 ChatGPT 4.1 翻译