744.计算得分

markdown
复制
1# 计算得分 题解
2
3## 题目分析
4
5我们有一个长度为 $m$ 的小写字母字符串，和一个长度为 $n$ 的计分序列 $A$。  
6我们需要将字符串划分成若干不重叠的部分，其中某些部分是由连续的 $k$ 个 `"abc"` 拼接而成的子串（$1 \le k \le n$），每一段这样的子串可以获得 $a_k$ 分。未被划分进任何得分子串的字符不得分。目标是最大化总得分。
7
8这是典型的 **序列划分型动态规划** 问题：在每个位置可以选择将前面一段形如 `abcabc...` 的子串作为一个得分块，或者跳过当前字符。
9
10## 解题思路
11
12定义状态：
13
14> $dp[i]$：考虑字符串的前 $i$ 个字符（下标从 $1$ 开始）所能获得的最大得分。
15
16状态转移分两种情况：
17
181. **不使用第 $i$ 个字符**  
19   $dp[i] = dp[i-1]$
20
212. **使用一个以 $i$ 结尾的、“abc”重复 $j$ 次的子串**  
22   若子串 $s[i-3j+1 \dots i]$ 恰好等于 $j$ 个 `"abc"` 拼接，则可以从 $dp[i-3j]$ 转移过来：
23   $$dp[i] = \max\Big(dp[i],\ dp[i-3j] + a_j\Big), \quad 1 \le j \le n$$
24
25最终答案即为 $dp[m]$。
26
27### 如何快速判断子串是否由 $j$ 个 `"abc"` 组成
28
29令 $len[i]$ 表示以位置 $i$ 结尾的、最长连续 `"abc"` 的个数。
30
31递推方式如下：
32- 若 $s[i-2] = \text{'a'},\ s[i-1] = \text{'b'},\ s[i] = \text{'c'}$，说明以 $i-2$ 开始有一个新的 `"abc"`，它可以接在前面结束于 $i-3$ 的连续段后面，因此：
33  $$len[i] = len[i-3] + 1$$
34- 否则，$len[i] = 0$。
35
36这样我们只需要 $O(m)$ 时间就能预处理出所有 $len[i]$。  
37对于以 $i$ 结尾的状态，枚举 $j$ 从 $1$ 到 $\min(n, len[i])$ 即可进行转移。
38
39### 与参考代码的对比
40
41题目给出的参考代码在枚举 $j$ 时使用了：
42
43```cpp
44if(s.substr(l,3) == "abc"){
45    dp[i]=max(dp[i], dp[l]+a[j]);
46} else break;

这一写法只检查了待选子串最前面的三个字符，并没有完全验证整个子串是由 $j$ 个 "abc" 拼接。
虽然在特定数据下可能通过，但从严谨性出发，应该检查整段或者使用预处理的 $len[i]$ 来保证正确性。

本解析给出的方法是 预处理最长连续 abc 个数，既保证了正确性，又降低了常数。

算法流程

1. 读入 $n$、数组 $a$、$m$ 和字符串 $s$（下标从 $1$ 开始方便处理）。
2. 预处理 $len$ 数组：
   • 初始 $len[i] = 0$。
   • 对于 $i$ 从 $3$ 到 $m$，如果 $s[i-2]\,s[i-1]\,s[i]$ 等于 "abc"，则 $len[i] = len[i-3] + 1$。
3. 动态规划：
   • $dp[0] = 0$
   • 对于 $i$ 从 $1$ 到 $m$：
     • $dp[i] = dp[i-1]$ （不使用当前字符）
     • 对于 $j$ 从 $1$ 到 $\min(n, len[i])$：
       • $dp[i] = \max(dp[i],\ dp[i - 3j] + a[j])$
4. 输出 $dp[m]$。

时间复杂度分析

• 预处理 $len$ 数组：$O(m)$。
• DP 转移：对于每个 $i$（共 $m$ 个），最多枚举 $n$ 次 $j$，每次 $O(1)$。
  总复杂度 $O(n \cdot m)$。
  根据数据范围 $n \le 20$，$m \le 10^5$，最大操作次数约 $2\times10^6$，完全可以在 1 秒内运行完成。
• 空间复杂度：$dp$ 数组和 $len$ 数组均需要 $O(m)$ 空间，符合内存限制。

参考代码

以下是采用预处理 $len$ 数组的正确实现（C++）：

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1e5 + 10;
5int a[25], dp[N], len[N];
6char s[N];
7
8int main() {
9    ios::sync_with_stdio(false);
10    cin.tie(nullptr);
11
12    int n, m;
13    cin >> n;
14    for (int i = 1; i <= n; ++i) {
15        cin >> a[i];
16    }
17    cin >> m;
18    cin >> (s + 1);  // 从下标 1 开始读入
19
20    // 预处理 len[i]：以 i 结尾的最长连续 "abc" 个数
21    for (int i = 3; i <= m; ++i) {
22        if (s[i - 2] == 'a' && s[i - 1] == 'b' && s[i] == 'c') {
23            len[i] = len[i - 3] + 1;
24        }
25    }
26
27    // 动态规划
28    for (int i = 1; i <= m; ++i) {
29        dp[i] = dp[i - 1];                     // 不使用 s[i]
30        for (int j = 1; j <= n; ++j) {
31            if (j > len[i]) break;             // 不存在 j 个连续的 abc
32            int prev = i - 3 * j;
33            if (prev >= 0) {                   // 注意边界，0 代表空前缀
34                dp[i] = max(dp[i], dp[prev] + a[j]);
35            }
36        }
37    }
38
39    cout << dp[m] << "\n";
40    return 0;
41}

代码解释

• s + 1：让字符串下标从 $1$ 开始，方便与 $dp$ 下标对齐。
• len[i] 记录以 $i$ 结尾的最长连续 "abc" 段个数，借助 len[i-3] 实现了 $O(1)$ 转移。
• DP 中 j > len[i] 时 break：因为 $j$ 递增，一旦超出现有最长连续长度，更大的 $j$ 必然也不满足。
• prev = i - 3 * j 是得分子串的起始前一个位置，若 prev == 0 表示子串从字符串开头开始，此时 $dp[0]=0$。
• 最终输出 $dp[m]$ 即为答案。

该实现简洁高效，满足题目所有数据范围，并正确处理了所有合法情况。