← 返回题目列表

AtCoder · agc066_d

D. 独立套装

中文机器翻译题面 查看原题

分数: 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.