A32224. 计算得分题面描述小杨想要计算由m个小写字母组成的字符串的得分。小杨设置了一个包含n个正整数的计分序列A=[a1,a2,.....an]，如果字符串的一个子串由k(1<=k<=n) 个 abc 首尾相接组成，那么能够得到分数ak，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。例如，假设n=3，字符串 dabcabcabcabzabc 的所有可能计分方式如下：d+abc+…
填空题
困难
知识点
题目描述
计算得分
题面描述
小杨想要计算由m个小写字母组成的字符串的得分。
小杨设置了一个包含n个正整数的计分序列A=[a1,a2,.....an]，如果字符串的一个子串由k(1<=k<=n) 个 abc 首尾相接组成，那么能够得到分数ak，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设n=3，字符串 dabcabcabcabzabc 的所有可能计分方式如下：
d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为 a1 + a2 + a3
d+abc+abc+abc+abz+abc，总得分为 a1 + a1 + a1 + a1
d+abcabcabc+abz+abc，总得分为 a3 + a1
小杨想知道对于给定的字符串，最大总得分是多少。
输入格式
第一行包含一个正整数 n，代表计分序列A的长度。
第二行包含 n 个正整数，代表计分序列A。
第三行包含一个正整数m，代表字符串的长度。
第四行包含一个由m个小写字母组成的字符串。
输出格式
输出一个整数，代表给定字符串的最大总得分。
样例1
输入
3
312
13
dabcabcabcabz
输出
9
样例解释
最优的计分方式为 d+abc+abc+abc+abz，总得分为 a1 + a1 + a1，共9分。
数据范围
对于全部数据，保证有 1 <= n <= 20，1 <= m <= 105， 1 <= ai <= 1000。
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[30];
string s;
int dp[N];
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
int m;
cin>>m;
cin>>s;
for(int i=1; i<=m; i++) {
dp[i]=dp[i-1];
for(int j=1; j<=n; j++) {
if(i-3*j+1<=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<<dp[m]<<"\n";
}
上一题
下一题