计算得分 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨想要计算由m个小写字母组成的字符串的得分。 小杨设置了一个包含n个正整数的计分序列A=…
计算得分
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨想要计算由m个小写字母组成的字符串的得分。
小杨设置了一个包含n个正整数的计分序列A=[a1,a2,...,an],如果字符串的一个子串由k(1≤k≤n) 个 abc 首尾相接组成,那么能够得到分数ak,并且字符串包含的字符不能够重复计算得分,整个字符串的得分是计分子串的总和。
例如,假设a=3,字符串 dabcabcabcabzabc 的所有可能计分方式如下:d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc,其中 d 和 abz 不计算得分,总得分为a1+a2+a1d+abc+abc+abc+abz+abc,总得分为a1+a1+a1+a1d+abcabcabc+abz+abc,总得分为a3+a1
小杨想知道对于给定的字符串,最大总得分是多少。
输入格式
第一行包含一个正整数n,代表计分序列 A 的长度。
第二行包含 n 个正整数,代表计分序列A。
第三行包含一个正整数m,代表字符串的长度。
第四行包含一个由 m 个小写字母组成的字符串。
输出格式
输出一个整数,代表给定字符串的最大总得分。
输入样例
输出样例
样例解释
最优的计分方式为 d+abc+abc+abc+abz,总得分为a1+a1+a1,共9 分。
数据范围

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-3j]+A[j]); i-3j+1>=1