题目描述
小杨想要计算由 m 个小写字母组成的字符串的得分。
小杨设置了一个包含 n 个正整数的计分序列 A=[a1,a2,…,an]，如果字符串的一个子串由 k(1≤k≤n) 个 abc 首尾相接组成，那么能够得到分数 ak，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设 ，字符串 dabcabcabcabzabc 的所有可能计分方式如下：
- d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为 a1+a2+a1。
- d+abc+abc+abc+abz+abc，总得分为 a1+a1+a1+a1。
- d+abcabcabc+abz+abc，总得分为 a3+a1。
小杨想知道对于给定的字符串，最大总得分是多少。
输入格式
-
第一行包含一个正整数 n，代表计分序列 A 的长度。
-
第二行包含 n 个正整数，代表计分序列 A。
-
第三行包含一个正整数 m，代表字符串的长度。
-
第四行包含一个由 m 个小写字母组成的字符串。
输出格式
输出一个整数，代表给定字符串的最大总得分。
输入输出样例
输入 #1
3 3 1 2 13 dabcabcabcabz
输出 #1
9
说明/提示
样例解释
最优的计分方式为 d+abc+abc+abc+abz，总得分为 a1+a1+a1，共 9 分。
数据范围
| 子任务编号 | 数据点占比 | n | m | ai | 特殊性质 |
|---|---|---|---|---|---|
| 1 | 20% | 20 | 10^5 | 1000 | 有 |
| 2 | 40% | 3 | 10^5 | 1000 | 无 |
| 3 | 40% | 20 | 10^5 | 1000 | 无 |
对于全部数据，保证有 1≤n≤20，1≤m≤10^5，1≤ai≤1000。
【题目大意】
给定字符串m,将其匹配abc字符串，连续的abc衔接的个数会有不同的得分，求解字符串m的最大的得分。
【考纲知识点】
一维动态规划
【解题思路】
20分思路，考虑到ai>=ai+1,此时将abc单独算是最多的，答案为A[1]*abc的个数。
满分思路
状态表示:DP[i]表示前i个字符组成的最大得分。
状态转移方程:
对第i个字符，有两种情况：①不作为答案的一部分。②作为abc的一部分对答案产生贡献；
对于①:DP[i]=DP[i-1] (也可以理解为将i-1的答案顺延到i)，这保证了答案为DP[m]
对于②:前i个字符中，最后一个位置作为“abc”，可以考虑用连续的j个abc连接更新答案；
此时i-3*j+1 ~i的范围都为连续的j个abc，产生的代价为A[j]
转态转移方程为:
DP[i]=DP[i-3*j]+A[j]
①和②构成了答案的所有解
有:DP[i]=max(DP[i-1],max(DP[i-3*j]+A[j]); i-3*j+1>=1
参考程序