#P13116. [AGC066D] A Independent Set

[AGC066D] A Independent Set

题目描述

给定一个由 A 和 B 组成、长度为 NN 的字符串 SS。保证 SS 中 A 的个数不超过 N+12\frac{N+1}{2}。此外,给定一个正整数序列 (x1, …, xN−1)(x_1,\ \ldots,\ x_{N-1})。

你可以对该字符串重复进行如下操作:

  • 选择满足 1≤i≤N−11\leq i\leq N-1 的整数 ii,交换 SS 的第 ii 个字符和第 i+1i+1 个字符。该操作的代价为 xix_i。

你的目标是使 SS 中任意两个 A 不相邻。请你求出为达成目标所需的总代价的最小值。

有 TT 组测试数据,请分别输出每组的答案。

输入格式

输入按以下格式从标准输入给出。

TT
case1\text{case}_1
⋮\vdots
caseT\text{case}_T

每组测试数据格式如下:

NN SS x1x_1 …\ldots xN−1x_{N-1}

输出格式

请输出 TT 行,第 ii 行输出第 ii 组测试数据中,为使 SS 中任意两个 A 不相邻所需的最小总代价。

输入输出样例 #1

输入 #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

说明/提示

限制条件

  • 1≤T≤1051\leq T\leq 10^5
  • 2≤N≤1062\leq N\leq 10^6
  • SS 是由 A 和 B 组成的长度为 NN 的字符串。
  • SS 中 A 的个数不超过 N+12\frac{N+1}{2}。
  • 1≤xi≤1061\leq x_i\leq 10^6
  • 所有测试数据中 NN 的总和不超过 10610^6。

样例解释 1

  • 对于第 11 组测试数据,通过对 i=1i=1 进行操作,SS 由 BAAB 变为 ABAB,目标达成,总代价为 x1=3x_1=3。
  • 对于第 22 组测试数据,不进行任何操作即可达成目标,总代价为 00。
  • 对于第 33 组测试数据,通过对 i=1i=1、i=4i=4 进行操作,SS 由 BAAABBB 变为 ABAABBB,再变为 ABABABB,目标达成,总代价为 x1+x4=13x_1+x_4=13。
  • 对于第 44 组测试数据,通过对 i=4i=4、i=3i=3、i=5i=5 进行操作,SS 由 BAAABBB 变为 BAABABB,再变为 BABAABB,再变为 BABABAB,目标达成,总代价为 x4+x3+x5=15x_4+x_3+x_5=15。