A7696 · Celester · GESP考级

题目描述

接下来 $N$ 天的天气情况由字符串 $S$ 给出。 若 $S$ 的第 $i$ 个字符为 S，则第 $i$ 天为晴天；若为 R，则第 $i$ 天为雨天。 此外，你当前的幸福感为 $0$。 你可以执行以下操作任意多次（包括零次）： * 选择一个整数 $i$，满足 $1 \le i \le N$。 * 若第 $i$ 天天气为晴天，则将其改为雨天；若为雨天，则改为晴天。 * 然而，若你更改了第 $i$ 天的天气，则你的幸福感减少 $X_i$。 执行完所有操作后，你的幸福感将根据最终天气按如下规则增加： * 对每个满足 $1 \le i \le N-1$ 的整数 $i$，若第 $i$ 天（修改后）为雨天且第 $i+1$ 天为晴天，则你的幸福感增加 $Y_i$。 求通过执行操作所能达到的最大幸福感值。 共给出 $T$ 组测试用例，请分别求解。

输入格式

输入从标准输入给出，格式如下，其中 $\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

A7696 | Celester

题目描述

输入格式

输出格式

输入输出样例

A7696 | $Celester$