简答题 偏难
#21104

计算得分 时间限制: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 个小写字母组成的字符串。

输出格式

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


输入样例

3
3 1 2
13
dabcabcabcabz

输出样例

9

样例解释

最优的计分方式为 d+abc+abc+abc+abz,总得分为a1+a1+a1,共9 分。

数据范围

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; int a[30]; string s; int dp[N]; int main(){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; } int m; cin&gt;&gt;m; cin&gt;&gt;s; for(int i=1;i&lt;=m;i++){ dp[i]=dp[i-1]; for(int j=1;j&lt;=n;j++){ if(i-3*j+1&lt;=0)break; int l = i-3*j+1; if(s.substr(l-1,3)=="abc"){ dp[i]=max(dp[i],dp[l]+a[j]); }else break; } } cout&lt;&lt;dp[m]&lt;&lt;"\n"; }</pre>
解析

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