AT_agc066_d [AGC066D] A Independent Set

给定一个由 `A` 和 `B` 组成、长度为 $N$ 的字符串 $S$。保证 $S$ 中 `A` 的个数不超过 $\frac{N+1}{2}$。此外，给定一个正整数序列 $(x_1,\ \ldots,\ x_{N-1})$。 你可以对该字符串重复进行如下操作： - 选择满足 $1\leq i\leq N-1$ 的整数 $i$，交换 $S$ 的第 $i$ 个字符和第 $i+1$ 个字符。该操作的代价为 $x_i$。 你的目标是使 $S$ 中任意两个 `A` 不相邻。请你求出为达成目标所需的总代价的最小值。 有 $T$ 组测试数据，请分别输出每组的答案。

输入按以下格式从标准输入给出。 > $T$ > $\text{case}_1$ > $\vdots$ > $\text{case}_T$ 每组测试数据格式如下： > $N$ $S$ $x_1$ $\ldots$ $x_{N-1}$

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据中，为使 $S$ 中任意两个 `A` 不相邻所需的最小总代价。

### 限制条件 - $1\leq T\leq 10^5$ - $2\leq N\leq 10^6$ - $S$ 是由 `A` 和 `B` 组成的长度为 $N$ 的字符串。 - $S$ 中 `A` 的个数不超过 $\frac{N+1}{2}$。 - $1\leq x_i\leq 10^6$ - 所有测试数据中 $N$ 的总和不超过 $10^6$。 ### 样例解释 1 - 对于第 $1$ 组测试数据，通过对 $i=1$ 进行操作，$S$ 由 `BAAB` 变为 `ABAB`，目标达成，总代价为 $x_1=3$。 - 对于第 $2$ 组测试数据，不进行任何操作即可达成目标，总代价为 $0$。 - 对于第 $3$ 组测试数据，通过对 $i=1$、$i=4$ 进行操作，$S$ 由 `BAAABBB` 变为 `ABAABBB`，再变为 `ABABABB`，目标达成，总代价为 $x_1+x_4=13$。 - 对于第 $4$ 组测试数据，通过对 $i=4$、$i=3$、$i=5$ 进行操作，$S$ 由 `BAAABBB` 变为 `BAABABB`，再变为 `BABAABB`，再变为 `BABABAB`，目标达成，总代价为 $x_4+x_3+x_5=15$。 由 ChatGPT 4.1 翻译