计算得分

题目描述

⼩杨想要计算由 个⼩写字母组成的字符串的得分。 ⼩杨设置了⼀个包含 个正整数的计分序列 ，如果字符串的⼀个⼦串由 ( ) 个 abc ⾸ 尾相接组成，那么能够得到分数 ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分⼦串的 总和。 例如，假设 ，字符串 dabcabcabcabzabc 的所有可能计分⽅式如下： d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为 d+abc+abc+abc+abz+abc，总得分为 d+abcabcabc+abz+abc，总得分为 ⼩杨想知道对于给定的字符串，最⼤总得分是多少。

输入格式

第⼀⾏包含⼀个正整数 ，代表计分序列 的长度。 第⼆⾏包含 个正整数，代表计分序列 。 第三⾏包含⼀个正整数 ，代表字符串的长度。 第四⾏包含⼀个由 个⼩写字母组成的字符串。

输出格式

输出⼀个整数，代表给定字符串的最⼤总得分。 3.1.4 样例1 1 3 2 3 1 2 3 13 4 dabcabcabcabz 1 9 3.1.5 样例解释 最优的计分⽅式为 d+abc+abc+abc+abz，总得分为 ，共 分。 3.1.6 数据范围 子任务编号 数据点占比 特殊条件 1 20% 对于所有的 ( ),存在 2 40% 3 40% 对于全部数据，保证有 。 3.1.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int a[30]; 5 string s; 6 int dp[N]; 7 int main(){ 8 int n; 9 cin>>n; 10 for(int i=1;i<=n;i++){ 11 cin>>a[i]; 12 } 13 int m; 14 cin>>m; 15 cin>>s; 16 for(int i=1;i<=m;i++){ 17 dp[i]=dp[i-1]; 18 for(int j=1;j<=n;j++){ 19 if(i-3j+1<=0)break; 20 int l = i-3j+1; 21 if(s.substr(l-1,3)=="abc"){ 22 dp[i]=max(dp[i],dp[l]+a[j]); 23 }else break; 24 } 25 } 26 cout<<dp[m]<<"\n"; 27 }

样例输入 #1

1 3
2 3 1 2
3 13
4 dabcabcabcabz
1 9

样例输出 #1

样例解释 #1

最优的计分⽅式为 d+abc+abc+abc+abz，总得分为 ，共 分。

数据范围

子任务编号 数据点占比 特殊条件 1 20% 对于所有的 ( ),存在 2 40% 3 40% 对于全部数据，保证有 。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。