欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10721 GESP202406 六级] 计算得分 - 洛谷
【题目描述】
小杨想要计算由m mm个小写字母组成的字符串的得分。
小杨设置了一个包含n nn个正整数的计分序列A = [ a 1 , a 2 , … , a n ] A=[a_1,a_2,\ldots,a_n]A=[a1,a2,…,an]，如果字符串的一个子串由k ( 1 ≤ k ≤ n ) k(1\leq k \leq n)k(1≤k≤n)个abc \texttt{abc}abc首尾相接组成，那么能够得到分数a k a_kak，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设 ，字符串dabcabcabcabzabc \texttt{dabcabcabcabzabc}dabcabcabcabzabc的所有可能计分方式如下：
- d+abc+abcabc+abz+abc \texttt{d+abc+abcabc+abz+abc}d+abc+abcabc+abz+abc或者d+abcabc+abc+abz+abc \texttt{d+abcabc+abc+abz+abc}d+abcabc+abc+abz+abc，其中d \texttt{d}d和abz \texttt{abz}abz不计算得分，总得分为a 1 + a 2 + a 1 a_1+a_2+a_1a1+a2+a1。
- d+abc+abc+abc+abz+abc \texttt{d+abc+abc+abc+abz+abc}d+abc+abc+abc+abz+abc，总得分为a 1 + a 1 + a 1 + a 1 a_1+a_1+a_1+a_1a1+a1+a1+a1。
- d+abcabcabc+abz+abc \texttt{d+abcabcabc+abz+abc}d+abcabcabc+abz+abc，总得分为a 3 + a 1 a_3+a_1a3+a1。
小杨想知道对于给定的字符串，最大总得分是多少。
【输入】
- 第一行包含一个正整数n nn，代表计分序列A AA的长度。
- 第二行包含n nn个正整数，代表计分序列A AA。
- 第三行包含一个正整数m mm，代表字符串的长度。
- 第四行包含一个由m mm个小写字母组成的字符串。
【输出】
输出一个整数，代表给定字符串的最大总得分。
【输入样例】
3 3 1 2 13 dabcabcabcabz【输出样例】
9【算法标签】
《洛谷 P10721 计算得分》 #动态规划DP# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn,m;// n: 物品数量, m: 字符串长度inta[25];// a[i]: 第i个物品的价值intf[100010];// f[i]: 前i个字符的最大价值string s;// 输入的字符串intmain(){// 输入物品数量cin>>n;// 输入每个物品的价值for(inti=1;i<=n;i++){cin>>a[i];}// 输入字符串长度和字符串cin>>m>>s;// 在字符串前加一个空格，使索引从1开始s=' '+s;// 动态规划计算最大价值for(inti=1;i<=m;i++)// 遍历每个字符位置{// 初始化：不匹配任何模式，继承前一个位置的值f[i]=f[i-1];// 尝试匹配每个物品for(intj=1;j<=n;j++){// 检查：当前位置i是否足够长来匹配长度为3*j的子串// 需要匹配3*j个字符，即"abc"重复j次if(i<3*j){break;// 长度不足，后面的j更大，更不可能匹配}// 提取以i结尾的长度为3的子串// 注意：这里代码有误，应该是提取长度为3*j的子串// 但实际代码中substr只提取3个字符if(s.substr(i-3*j+1,3)!="abc"){break;// 不匹配"abc"，停止尝试更大的j}// 如果匹配成功，更新最大价值f[i]=max(f[i],f[i-3*j]+a[j]);}}// 输出前m个字符的最大价值cout<<f[m]<<endl;return0;}【运行结果】
3 3 1 2 13 dabcabcabcabz 9
