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 翻译