3867 - 计算得分
题目描述
小杨想要计算由 m 个小写字母组成的字符串的得分。
小杨设置了一个包含 n 个正整数的计分序列 A=[a_1,a_2,...,a_n]，如果字符串的一个子串由 k(1 \le k \le n ) 个 abc 首尾相接组成，那么能够得到分数 a_k ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设 n=3，字符串 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
输出
9
说明
【样例解释】
最优的计分方式为 d+abc+abc+abc+abz，总得分为 a_1+a_1+a_1 ，共 9 分。
【数据范围】
对于全部数据，保证有 1 \le n \le 20，1 \le m \le 10^5，1 \le a_i \le 1000 。
来源
2024年GESP 6月认证C++六级真题
标签