g6-02679. GESP-6级-2024-06-计算得分

题目描述

小杨想要计算由 $m$ 个小写字母组成的字符串的得分。

小杨设置了一个包含 $n$ 个正整数的计分序列 $A = [a_{1}, a_{2}, \dots, a_{n}]$ ，如果字符串的一个子串由 $k (1 \leq k \leq n)$ 个 $abc$ 首尾相接组成，那么能够得到分数 $a_{k}$ ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设，字符串 $dabcabcabcabzabc$ 的所有可能计分方式如下：

$d+abc+abcabc+abz+abc$ 或者 $d+abcabc+abc+abz+abc$ ，其中 $d$ 和 $abz$ 不计算得分，总得分为 $a_{1} + a_{2} + a_{1}$ 。
$d+abc+abc+abc+abz+abc$ ，总得分为 $a_{1} + a_{1} + a_{1} + a_{1}$ 。
$d+abcabcabc+abz+abc$ ，总得分为 $a_{3} + a_{1}$ 。

小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

第一行包含一个正整数 $n$ ，代表计分序列 $A$ 的长度。
第二行包含 $n$ 个正整数，代表计分序列 $A$ 。
第三行包含一个正整数 $m$ ，代表字符串的长度。
第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

输出一个整数，代表给定字符串的最大总得分。

样例

输入

3
3 1 2
13
dabcabcabcabz

输出

数据范围

样例解释

最优的计分方式为 $d+abc+abc+abc+abz$ ，总得分为 $a_{1} + a_{1} + a_{1}$ ，共 $9$ 分。

数据范围

子任务编号	数据点占比	$n$	$m$	$a_{i}$	特殊性质
$1$	$20%$	$\leq 20$	$\leq 1 0^{5}$	$\leq 1000$	对于所有的 $i (1 \leq i \leq n)$ ，存在 $a_{i} \geq a_{i + 1}$
$2$	$40%$	$\leq 3$	$\leq 1 0^{5}$	$\leq 1000$
$3$	$40%$	$\leq 20$	$\leq 1 0^{5}$	$\leq 1000$

对于全部数据，保证有 $1 \leq n \leq 20$ ， $1 \leq m \leq 1 0^{5}$ ， $1 \leq a_{i} \leq 1000$ 。

来源：洛谷 P10721（CCF GESP 六级上机题）

g6-02679. GESP-6级-2024-06-计算得分 未做

题目描述

输入格式

输出格式

样例

数据范围

样例解释

数据范围

g6-02679. GESP-6级-2024-06-计算得分未做