题解：P10721 [GESP202406 六级] 计算得分（未成功）

博客食用更佳：My blog

题目传送门

分析：

这道题是一个标准的 dp。我们可以先预处理多个 \(\texttt{abc}\) 连成的字符串的最大值，之后可以按最长平台的方法处理。

步骤：

1. 初值：这题不需要赋值， 因为题目保证得分是正的，故初值为 \(0\)。

2. 状态：\(dp_i\) 表示连续 \(i\) 个 \(\texttt{abc}\) 组成的字符串的得分最大值。

3. 答案：最后跑一遍字符串，求出得分和。

4. 状态转移方程：枚举当前字符串拆分出的子串的长度，记作 \(j\)，状态转移方程就是 \(dp_i=dp_{i-j}+a_j\)。

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 / 3 + 5;
int dp[MAX], a[25], m, n, cnt, sum;
string s;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> m >> s;
	s = ' ' + s;
	for (int i = 1; i <= m / 3; i++)
		for (int j = 1; j <= min(n, i); j++)
			dp[i] = max(dp[i], dp[i - j] + a[j]);
	
	for (int i = 3; i <= m; ) {
		while(i <= m && s[i] == 'c' && s[i - 1] == 'b' && s[i - 2] == 'a') i += 3, cnt++;
		sum += dp[cnt], cnt = 0, i++;
	}
	cout << sum;
	return 0;
}