← 返回题目列表

AtCoder · abc464_d

D. 塞莱斯特

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

分数: 400 点

问题陈述

即将到来的天气 N 天以字符串形式给出 S.
如果 i- 第一个字符 S is S,然后是当天的天气 i 晴;如果是的话 R,然后是当天的天气 i 下雨了。
另外,你目前的幸福是 0.

您可以执行以下操作任意次数,可能为零:

  • 选择一个整数 i 与 1 \le i \le N.
  • 如果当天天气 i 晴,改为雨;如果下雨,就改为晴天。
  • 但是,如果当天天气发生变化 i,你的幸福感减少了 X_i.

执行操作后,您的幸福感会根据最终天气情况根据以下条件增加:

  • 对于每个整数 i 与 1 \le i \le N-1,如果当天天气 i 修改后当天天气下雨 i+1 晴天,你的幸福感增加 Y_i.

找出通过执行操作可实现的最大幸福值。

T 给出了测试用例;逐一解决。

约束

  • 1 \le T \le 10^4
  • N 是介于 2 和 2 \times 10^5,包括在内。
  • S 是一个长度为 N 组成 S 和 R.
  • X_i 是介于 1 和 10^9,包括在内。
  • Y_i 是介于 1 和 10^9,包括在内。
  • 总和 N 在单个输入中最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
S
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_{N-1}

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

示例输出 1

5
3
0
165
5201284760

此输入包含五个测试用例。

例如,对于第一个测试用例,您可以通过执行以下操作来最大化幸福感:

  • 更改当天的天气 3 从雨到晴。幸福感减少 X_3 = 4,每天的天气变成晴、雨、晴、雨、晴、雨。
  • 由于此操作,自当天起 2 下雨天 3 阳光明媚,幸福感增加 Y_2 = 6,从那天起 4 下雨天 5 阳光明媚,幸福感增加 Y_4 = 3.
  • 总的幸福是 (-4) + 6 + 3 = 5,这是可实现的最大值。

对于第二个和第三个测试用例,不执行任何操作可能是最佳的。

对于第五个测试用例,请注意答案可能不适合 32- 位整数类型。