[GESP202406 六级] 计算得分（含视频）

视频讲解[GESP202406 六级] 计算得分-信息学奥赛GESP等级考试真题解析一、原题题目描述小杨想要计算由 m 个小写字母组成的字符串的得分。小杨设置了一个包含 n 个正整数的计分序列 A[a1​,a2​,…,an​]如果字符串的一个子串由 k(1≤k≤n) 个 abc 首尾相接组成那么能够得到分数 ak​并且字符串包含的字符不能够重复计算得分整个字符串的得分是计分子串的总和。例如假设 字符串 dabcabcabcabzabc 的所有可能计分方式如下dabcabcabcabzabc 或者 dabcabcabcabzabc其中 d 和 abz 不计算得分总得分为 a1​a2​a1​。dabcabcabcabzabc总得分为 a1​a1​a1​a1​。dabcabcabcabzabc总得分为 a3​a1​。小杨想知道对于给定的字符串最大总得分是多少。输入格式第一行包含一个正整数 n代表计分序列 A 的长度。第二行包含 n 个正整数代表计分序列 A。第三行包含一个正整数 m代表字符串的长度。第四行包含一个由 m 个小写字母组成的字符串。输出格式输出一个整数代表给定字符串的最大总得分。输入输出样例输入 #13 3 1 2 13 dabcabcabcabz输出 #19说明/提示样例解释最优的计分方式为 dabcabcabcabz总得分为 a1​a1​a1​共 9 分。数据范围子任务编号数据点占比nmai​特殊性质120%≤20≤10^5≤1000对于所有的 i(1≤i≤n)存在 ai​≥ai1​240%≤3≤10^5≤1000340%≤20≤10^5≤1000对于全部数据保证有 1≤n≤201≤m≤1051≤ai​≤1000。二、做题思路1)填充数据#includebits/stdc.h using namespace std; int main(){ //1)填充数据 //1.1)确定最大长度n int n;cinn; //1.2)确定各个长度的分数 int a[25]{}; for(int i1;in;i) cina[i]; //1.3)确定字符串长度m int m;cinm; //1.4)填充字符串s string s;cins; return 0; }2)计算各个长度abc的出现#includebits/stdc.h using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 vectorint a_num; //2.1)从最长abc(不能超过20) 循环到 最短abc //制造出20个abc的拼接 string now; for(int i1;i20;i) nowabc; for(int i20;i1;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)动态规划计算当前长度的最优解#includebits/stdc.h using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 ///... //3)动态规划计算当前长度的最优解 //初始化dp vectorint dp(25,0); //循环每个长度的分数 for(int i1;i20;i){ //循环所有长度 for(int ji;j20;j){ dp[j]max(dp[j],dp[j-i]a[i]); } } return 0; }4)累加所有长度abc的最优解#includebits/stdc.h using namespace std; int main(){ //1)填充数据 //... //2)计算各个长度abc的出现 ///... //3)动态规划计算当前长度的最优解 //... //4)累加所有长度abc的最优解 long long ans0; for(auto it:a_num){ ansdp[it]; } coutans; return 0; }三、答案#includebits/stdc.h using namespace std; int main(){ //1)填充数据 //1.1)确定最大长度n int n;cinn; //1.2)确定各个长度的分数 int a[25]{}; for(int i1;in;i) cina[i]; //1.3)确定字符串长度m int m;cinm; //1.4)填充字符串s string s;cins; //2)计算各个长度abc的出现 vectorint a_num; //2.1)从最长abc(不能超过20) 循环到 最短abc //制造出20个abc的拼接 string now; for(int i1;i20;i) nowabc; for(int i20;i1;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 vectorint dp(25,0); //循环每个长度的分数 for(int i1;i20;i){ //循环所有长度 for(int ji;j20;j){ dp[j]max(dp[j],dp[j-i]a[i]); } } //4)累加所有长度abc的最优解 long long ans0; for(auto it:a_num){ ansdp[it]; } coutans; return 0; }