[GESP202406 六级] 计算得分

普及/提高- GESP 六级 真题

题目描述

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

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

例如,假设 ,字符串 $\texttt{dabcabcabcabzabc}$ 的所有可能计分方式如下:
- $\texttt{d+abc+abcabc+abz+abc}$ 或者 $\texttt{d+abcabc+abc+abz+abc}$,其中 $\texttt{d}$ 和 $\texttt{abz}$ 不计算得分,总得分为 $a_1+a_2+a_1$。
- $\texttt{d+abc+abc+abc+abz+abc}$,总得分为 $a_1+a_1+a_1+a_1$。
- $\texttt{d+abcabcabc+abz+abc}$,总得分为 $a_3+a_1$。

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

输入格式

  • 第一行包含一个正整数 $n$,代表计分序列 $A$ 的长度。

  • 第二行包含 $n$ 个正整数,代表计分序列 $A$。

  • 第三行包含一个正整数 $m$,代表字符串的长度。

  • 第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

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

数据范围

样例解释

最优的计分方式为 $\texttt{d+abc+abc+abc+abz}$,总得分为 $a_1+a_1+a_1$,共 $9$ 分。

数据范围

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

对于全部数据,保证有 $1\leq n\leq 20$,$1\leq m\leq 10^5$,$1\leq a_i\leq 1000$。

样例输入 1

3
3 1 2
13
dabcabcabcabz

样例输出 1

9
时间限制: 1000ms
内存限制: 256MB
通过率: 0.0%
提交数: 0

设置

导航栏小工具

时钟
显示实时时钟(默认组件)
📝
代码粘贴板
快速创建和分享代码片段