![[GESP202406 六级] 计算得分（含视频）](http://pic.xiahunao.cn/yaotu/[GESP202406 六级] 计算得分（含视频）)
视频讲解：[GESP202406 六级] 计算得分-信息学奥赛GESP等级考试真题解析
一、原题
题目描述
小杨想要计算由 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 | 对于所有的 i(1≤i≤n)，存在 ai≥ai+1 |
| 2 | 40% | ≤3 | ≤10^5 | ≤1000 | |
| 3 | 40% | ≤20 | ≤10^5 | ≤1000 |
对于全部数据，保证有 1≤n≤20，1≤m≤105，1≤ai≤1000。
二、做题思路
1)填充数据
#include<bits/stdc++.h> using namespace std; int main(){ //1)填充数据 //1.1)确定最大长度n int n;cin>>n; //1.2)确定各个长度的分数 int a[25]={}; for(int i=1;i<=n;i++) cin>>a[i]; //1.3)确定字符串长度m int m;cin>>m; //1.4)填充字符串s string s;cin>>s; return 0; }2)计算各个长度abc的出现
#include<bits/stdc++.h> using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 vector<int> a_num; //2.1)从最长abc(不能超过20) 循环到 最短abc //制造出20个abc的拼接 string now=""; for(int i=1;i<=20;i++) now+="abc"; for(int i=20;i>=1;i--){ //2.2)找的到 存储 并替换成"1"(防止拼凑出新的abc) while(s.find(now)!=string::npos){ s.replace(s.find(now),now.size(),"1"); a_num.push_back(i); } now.erase(0,3); } return 0; }3)动态规划：计算当前长度的最优解
#include<bits/stdc++.h> using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 ///... //3)动态规划：计算当前长度的最优解 //初始化dp vector<int> dp(25,0); //循环每个长度的分数 for(int i=1;i<=20;i++){ //循环所有长度 for(int j=i;j<=20;j++){ dp[j]=max(dp[j],dp[j-i]+a[i]); } } return 0; }4)累加所有长度abc的最优解
#include<bits/stdc++.h> using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 ///... //3)动态规划：计算当前长度的最优解 //... //4)累加所有长度abc的最优解 long long ans=0; for(auto it:a_num){ ans+=dp[it]; } cout<<ans; return 0; }三、答案
#include<bits/stdc++.h> using namespace std; int main(){ //1)填充数据 //1.1)确定最大长度n int n;cin>>n; //1.2)确定各个长度的分数 int a[25]={}; for(int i=1;i<=n;i++) cin>>a[i]; //1.3)确定字符串长度m int m;cin>>m; //1.4)填充字符串s string s;cin>>s; //2)计算各个长度abc的出现 vector<int> a_num; //2.1)从最长abc(不能超过20) 循环到 最短abc //制造出20个abc的拼接 string now=""; for(int i=1;i<=20;i++) now+="abc"; for(int i=20;i>=1;i--){ //2.2)找的到 存储 并替换成"1"(防止拼凑出新的abc) while(s.find(now)!=string::npos){ s.replace(s.find(now),now.size(),"1"); a_num.push_back(i); } now.erase(0,3); } //3)动态规划：计算当前长度的最优解 //初始化dp vector<int> dp(25,0); //循环每个长度的分数 for(int i=1;i<=20;i++){ //循环所有长度 for(int j=i;j<=20;j++){ dp[j]=max(dp[j],dp[j-i]+a[i]); } } //4)累加所有长度abc的最优解 long long ans=0; for(auto it:a_num){ ans+=dp[it]; } cout<<ans; return 0; }
