分数: 1100 点
问题陈述
给你一个字符串 S 长度 N 组成 A 和 B。保证了数量 A中 S 最多是 \frac{N+1}{2}。此外,还给你一个正整数序列 (x_1, \ldots, x_{N-1}).
在此字符串上,您可以重复执行以下操作:
- 选择一个整数 i 这样 1\leq i\leq N-1,并交换 i-th 和 (i+1)- 第一个字符 S。该操作的成本是 x_i.
你的目标是重新排列 S 这样就没有两个 A是相邻的。找出实现这一目标所需的最低总成本。
T 给出了测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- 2\leq N\leq 10^6
- S 是一个长度为的字符串 N 组成
A和B. - 数量
A中 S 最多是 \frac{N+1}{2}. - 1\leq x_i \leq 10^6
- 总和 N 单个输入中的所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N
S
x_1 \ldots x_{N-1}
输出
打印 T 行。的 i- 第行应包含重新排列所需的最小总成本 S 这样就没有两个 As 是相邻的 i- 第一个测试用例。
示例输入 1
5 4 BAAB 3 4 5 5 BBBBB 1 2 3 4 7 BAAABBB 8 7 6 5 4 3 7 BAAABBB 100 7 6 5 4 3 20 BAABAABBBABAAABBBABB 12 85 37 44 25 14 36 29 71 53 15 47 13 80 14 74 53 76 19
示例输出 1
3 0 13 15 133
- 对于第一个测试用例,执行操作 i=1 变化 S as
BAAB→ABAB,实现目标。这种情况下的总成本是 x_1=3. - 对于第二个测试用例,不执行任何操作都无法实现目标。这种情况下的总成本是 0.
- 对于第三个测试用例,执行操作 i=1 和 i=4 变化 S as
BAAABBB→ABAABBB→ABABABB,实现目标。这种情况下的总成本是 x_1+x_4=13. - 对于第四个测试用例,执行操作 i=4, i=3,和 i=5 变化 S as
BAAABBB→BAABABB→BABAABB→BABABAB,实现目标。这种情况下的总成本是 x_4+x_3+x_5=15.