D - A Independent Set Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1100 点

問題文

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 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 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
  • 1 個の入力に含まれるテストケースについて，それらの N の総和は 10^6 以下である．

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

N
S
x_1 \ldots x_{N-1}

出力

T 行出力してください．i 行目には i 番目のテストケースについて，S において A が隣接しないようにするために必要なコストの最小値を出力してください．

入力例 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 番目のテストケースについて，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 です．

Score: 1100 points

Problem Statement

You are given a string S of length N consisting of A and B. It is guaranteed that the number of As in S is at most \frac{N+1}{2}. Additionally, you are given a sequence of positive integers (x_1, \ldots, x_{N-1}).

On this string, you can repeatedly perform the following operation:

  • Choose an integer i such that 1\leq i\leq N-1, and swap the i-th and (i+1)-th characters of S. The cost of this operation is x_i.

Your goal is to rearrange S so that no two As are adjacent. Find the minimum total cost required to achieve this goal.

T test cases are given; solve each of them.

Constraints

  • 1\leq T\leq 10^5
  • 2\leq N\leq 10^6
  • S is a string of length N consisting of A and B.
  • The number of As in S is at most \frac{N+1}{2}.
  • 1\leq x_i \leq 10^6
  • The sum of N over all test cases in a single input is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

N
S
x_1 \ldots x_{N-1}

Output

Print T lines. The i-th line should contain the minimum total cost required to rearrange S so that no two As are adjacent for the i-th test case.

Sample Input 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

Sample Output 1

3
0
13
15
133
  • For the first test case, performing the operation with i=1 changes S as BAAB → ABAB, achieving the goal. The total cost in this case is x_1=3.
  • For the second test case, performing nothing achieves the goal. The total cost in this case is 0.
  • For the third test case, performing the operation with i=1 and i=4 changes S as BAAABBB → ABAABBB → ABABABB, achieving the goal. The total cost in this case is x_1+x_4=13.
  • For the fourth test case, performing the operation with i=4, i=3, and i=5 changes S as BAAABBB → BAABABB → BABAABB → BABABAB, achieving the goal. The total cost in this case is x_4+x_3+x_5=15.