GESP 题解库 / 6 级题解 / [GESP202406 六级] 计算得分 · 第 16 / 27 题
GESP202406 六级 · P10721 · 中等

计算得分

选出若干不重叠的"abc 连块",使按长度计分的总分最大。

📊
n ≤ 20, m ≤ 10⁵
数据规模
🔢
long long
分值范围
⚡
O(nm)
时间复杂度
🎯
前缀 DP + 连块枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定字符串 S(长度 m)和计分序列 A[1..n]。若一个子串由 k 个 abc 首尾相接组成,则能得 a_k 分。不同计分子串的字符不能重叠,总分是所有计分子串得分之和。求最大总分。

💡
人话翻译:可计分的子串只有一种形式——abc、abcabc、abcabcabc…(即若干个连续的 abc 拼起来)。
设 dp[i] = 前 i 个字符能拿到的最大总分。转移有两条路:① 第 i 个字符不参与计分 → dp[i] = dp[i−1];② 以第 i 个字符结尾、长度为 3k 的块可计分 → dp[i] = dp[i−3k] + a_k。
由于 n ≤ 20,k 只需枚举 1 ~ 20,整体复杂度 O(nm) = 2 × 10⁶,非常轻松。

🔍 关键词提取

前缀 DP不重叠选择连块枚举n 小是突破口

已知条件

项目说明
输入第一行 n;第二行 A;第三行 m;第四行字符串 S
输出最大总分
数据范围1 ≤ n ≤ 20,1 ≤ m ≤ 10⁵
分值1 ≤ aᵢ ≤ 1000
约束计分子串之间字符不能重复使用

需要解决的问题

02
思维导图
整理解题思路的全貌
📝 dp[i] = max(dp[i−1], dp[i−3k] + a_k)
🧱 预处理单位
unit[i] 表示 S[i..i+2] 是否为 "abc"
只有这些位置能作为块的起点
块必须由连续单位组成
不同单位间不重叠
🧠 状态定义
dp[i]:前 i 个字符的最大总分
dp[0] = 0
答案 = dp[m]
按前缀长度递推
🔁 转移
方案一:不用第 i 个字符 → dp[i−1]
方案二:以 i 结尾取长度 3k 的块
要求这 k 个单位连续
n ≤ 20,所以 k 只枚举 1 ~ 20
⚠️ 易错点
块内部含非 abc 字符(必须逐单位校验)
把不连续的单位当成一块
忘记"不使用该字符"这条转移
用 int(总分可达 2 × 10⁷,安全但建议 long long)
03
样例手算推导
样例的完整推演

🧮 样例:n = 3,A = [3, 1, 2],S = "dabcabcabcabz"

先标出所有 abc 单位(下标从 1 开始)。

起点覆盖下标内容是否单位
22–4abc✓
55–7abc✓
88–10abc✓
1111–13abz✗

单位 2、5、8 连续(间隔恰好 3)→ 构成一个长度 3 的"连块"

1
这个连块可以怎么切?

整块取 k = 3 → a₃ = 2 分

切成 1 + 2 或 2 + 1 → a₁ + a₂ = 3 + 1 = 4 分

切成 1 + 1 + 1 → 3 × a₁ = 3 × 3 = 9 分 ← 最大

(注意块不能跨过 "abz",因为那不是 abc)

最优 9 分

2
DP 逐步计算

dp[0..3] = 0(前三个字符构不成完整块)

dp[4] = max(dp[3], dp[1] + a₁) = max(0, 3) = 3

dp[7] = max(dp[6], dp[4] + a₁, dp[1] + a₂)

= max(3, 3 + 3, 0 + 1) = 6

dp[10] = max(dp[9], dp[7]+a₁, dp[4]+a₂, dp[1]+a₃)

= max(6, 9, 4, 2) = 9

dp[11..13] = 9(后面没有可计分的块)

✅ 答案 9

9 ✓ 与样例一致(d + abc + abc + abc + abz)

🔑
注意这个关键点:块必须由"连续的 abc 单位"组成。样例里 abz 不是单位,所以任何跨越它的块都不合法。
实现时最稳的做法是:从 i 往前每次退 3 个字符,检查这一段是否等于 "abc";一旦不相等就立即停止枚举(因为更长的块也不可能合法了)。

🧮 为什么内层循环可以不写成 O(m)

这是本题复杂度能过关的核心原因。

1
如果 n 很大

若 n 也达到 10⁵,那么对每个 i 都要枚举 k = 1..O(i/3)

复杂度变成 O(m²/3) ≈ 3 × 10⁹

会超时

n 大时不可行

2
本题 n ≤ 20

k 只需枚举 1 ~ 20

因此每个 i 的内层最多 20 次

总计 20 × 10⁵ = 2 × 10⁶

非常轻松

✅ O(nm)

📊 复杂度对照

内层枚举范围总运算量(m = 10⁵)可行性
k = 1 ~ n(≤ 20)2 × 10⁶✅ 轻松
k = 1 ~ i/3(最坏)约 3 × 10⁹❌ 超时
⚠️
这道题的"数据范围"就是解法提示:题目特意把 n 限得很小(≤ 20)、而 m 很大(10⁵)。
这种"一大一小"的范围组合,通常意味着"外层扫大维度、内层只枚举小维度"。本题正是如此。
04
解法对比
前缀 DP O(nm) vs 搜索所有切法

⚔️ 解法对比

🟢 前缀 DP(推荐) 推荐

dp[i] 考虑"不用第 i 符"与"以 i 结尾取 3k 长的块"

  • 时间 O(nm) = 2 × 10⁶
  • 代码 25 行
  • 空间 O(m)
  • n ≤ 20 使内层极短
💡
内层校验的写法:从 i 往前每退 3 个字符检查一次是否等于 "abc",一旦不符合立即 break——因为"更长的块"必然也包含这段不合法的部分。

🟠 搜索所有划分方式

枚举每段的切分与长度,递归求最大

  • 划分方式指数级
  • m = 10⁵ 完全不可行
  • 只能处理 m ≤ 20 左右
  • 不适合
⚠️
为什么必须用 DP:"在序列上选不重叠区间求最大权"这类问题,几乎都用"前缀 DP + 枚举最后一段"。搜索只在 m 极小时可行。

📈 性能对比

方案复杂度可行性
前缀 DPO(nm)✅ 稳过
搜索切分指数级❌ 不可行
05
算法流程图
前缀 DP 并逐段校验连块
开始读入 n、A、m、字符串 S;dp[0] = 0i 从 1 遍历到 mdp[i] = dp[i − 1](第 i 个字符不计分)k 从 1 开始递增(最多到 n),j = i − 3kj 是否不小于 0 且 S[j..j+2] 等于 abc?是 ✓dp[i] = max(dp[i], dp[j] + a[k]),继续增大 k否 ✗立即停止枚举 k所有 i 处理完后输出 dp[m]结束i 加 1 递推下一个前缀
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📝 最大得分

第一行输入各 k 的分值,第二行输入字符串,程序会算出最大总分。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

long long a[25], dp[100005];
char s[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    int m;
    scanf("%d", &m);
    scanf("%s", s + 1);                       // 1-based,方便 dp 按"前 i 个字符"定义

    dp[0] = 0;

    for (int i = 1; i <= m; i++) {
        dp[i] = dp[i - 1];                    // 方案一:第 i 个字符不计分

        // 方案二:以 i 结尾取长度为 3k 的块
        for (int k = 1; k <= n; k++) {
            int j = i - 3 * k;
            if (j < 0) break;
            // 检查 S[j+1 .. j+3] 是否为 "abc"(该块的最后一节)
            if (!(s[j + 1] == 'a' && s[j + 2] == 'b' && s[j + 3] == 'c')) break;

            dp[i] = max(dp[i], dp[j] + a[k]);
        }
    }

    printf("%lld\n", dp[m]);
    return 0;
}
🔑
为什么"检查最后一节不是 abc 就可以 break"?因为长度为 3k 的块,它末尾那一节必须是 abc。
如果连末尾这一节都不是 abc,那么长度更长(k 更大)的块也一定不合法(它们都以同样的一节结尾)。所以可以安全地提前退出,把内层循环压得更短。

📖 关键几行怎么看

代码作用为什么这样写
dp[i] = dp[i-1]方案一不用第 i 个字符
for (k = 1; k <= n; k++)枚举块大小n ≤ 20,内层极短
j = i − 3k起点长度 3k 的块起点
if (!(s[j+1]==a && ...)) break;合法性校验末尾不是 abc 则更长的块也不合法
dp[i] = max(dp[i], dp[j] + a[k])转移取块 + 之前的最优
⚠️
四个坑:① 忘记 dp[i] = dp[i−1] 这条转移(会导致必须"每段都计分"才能更新,漏解);② 内层不 break(会去检查不合法的长块,甚至用错的下标);③ 字符串下标混用 0/1 基;④ 以为 a_k 随 k 递增(题目没这个保证,必须都枚举)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
3 1 2
13
dabcabcabcabz
9题面样例(切成三段 abc)
3
3 1 2
6
abcabc
6两段 k=1 得 3+3=6,优于整段 k=2 的 1
1
5
3
abc
5恰好一个 abc 块
1
5
2
ab
0构不成 abc,得分 0
2
10 10
6
abcabc
20两个 k=1 的块,各得 10
2
10 1
6
abcabc
20同样切成两段更优(k=2 只给 1)
✅
自查清单:① 有不使用转移吗?② 内层 break 吗?③ 枚举了所有 k 吗?

🚨 易错点清单

⚠️
漏掉"不使用"这条转移:dp[i] 必须能继承 dp[i−1]。
⚠️
内层不 break:末尾不是 abc 时更长的块也不合法。
⚠️
以为 A 单调:a_k 不一定随 k 递增,必须枚举所有 k。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(nm)
空间复杂度
O(m)
n, m 最大
20 × 10⁵
运算量
约 2 × 10⁶

时间怎么算的?

空间都用在哪?

dp 数组长度 m+1,分值数组长度 n+1。

✅ 约 200 万次操作,瞬间完成。本题的关键是"看数据范围定算法":n 小、m 大 → 内层枚举 n。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 前缀 DP + 不重叠区间选择的通用骨架
dp[0] = 0;
for (int i = 1; i <= m; i++) {
    dp[i] = dp[i-1];                       // 不做任何事
    for (每个以 i 结尾的合法区间 [j+1, i])  // 本题里 j = i - 3k
        dp[i] = max(dp[i], dp[j] + 价值(该区间));
}
// 答案 = dp[m]

// 本题的合法区间:长度 3k、内容恰为 k 个连续的 abc
// 校验技巧:从末尾往前 3 个一组校验,不合法立即 break

// 类似的"区间不重叠取最大权"问题
// - 活动选择(按结束时间 DP)
// - 字符串分段计分
// - 任务调度取最大收益(需排序 + 二分)

// 若 n 也可以很大,就需要更高级的手段
// (如:只在"连块"内部做一次前缀 DP,按连块分段处理)
// 即先把字符串拆成若干"由连续 abc 组成"的极大连块,
// 每个连块内部是个独立的 unbounded 背包型 DP

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
前缀 DPdp[i] 表示前 i 位最优所有"序列上选不重叠区间"的问题
提前 break不合法后更长区间也不合法可行性具有单调性的枚举
看范围定算法小维度内层、大维度外层数据范围一大一小时的通法
🌟
思考题:本题的 n 只有 20,所以内层枚举 k 很轻松。如果 n 也放大到 10⁵,你会怎么优化?(提示:可以先把字符串切成若干"极大连块"(由连续 abc 组成的最长段),每个连块长度记作 L;在连块内部就变成"把 L 拆成若干份、使 Σ a[份大小] 最大"的完全背包问题,而连块之间互不影响。这样总复杂度由"所有连块长度的平方和"决定,在实践中通常远小于 m²。)