《P10721 [GESP202406 六级] 计算得分》

题目背景对应的选择、判断题试题 - GESP 202406 C 六级 - 洛谷有题题目描述小杨想要计算由 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 个小写字母组成的字符串。输出格式输出一个整数代表给定字符串的最大总得分。输入输出样例输入 #1复制3 3 1 2 13 dabcabcabcabz输出 #1复制9说明/提示样例解释最优的计分方式为 dabcabcabcabz总得分为 a1​a1​a1​共 9 分。数据范围子任务编号数据点占比nmai​特殊性质120%≤20≤105≤1000对于所有的 i(1≤i≤n)存在 ai​≥ai1​240%≤3≤105≤1000340%≤20≤105≤1000对于全部数据保证有 1≤n≤201≤m≤1051≤ai​≤1000。代码实现#include iostream #include vector #include string #include algorithm using namespace std; typedef long long ll; const int INF -1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } int m; string s; cin m s; ll total 0; int ptr 0; while (ptr m - 3) { if (s[ptr] a s[ptr1] b s[ptr2] c) { int L 0; int cur ptr; while (cur m - 3 s[cur] a s[cur1] b s[cur2] c) { L; cur 3; } ptr cur; vectorll dp(L 1, 0); for (int t 1; t L; t) { dp[t] INF; for (int k 1; k n k t; k) { dp[t] max(dp[t], dp[t - k] a[k]); } } total dp[L]; } else { ptr; } } cout total \n; return 0; }