选出若干不重叠的"abc 连块",使按长度计分的总分最大。
给定字符串 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。前缀 DP不重叠选择连块枚举n 小是突破口
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 A;第三行 m;第四行字符串 S |
| 输出 | 最大总分 |
| 数据范围 | 1 ≤ n ≤ 20,1 ≤ m ≤ 10⁵ |
| 分值 | 1 ≤ aᵢ ≤ 1000 |
| 约束 | 计分子串之间字符不能重复使用 |
(abc)^k 的(k ≤ n);可以用一个"单位"数组标记:unit[i] = 1 表示 S[i..i+2] == "abc"S[i−3k .. i−1] 恰好是 k 个连续的 abc,即这 k 个单位首尾相接先标出所有 abc 单位(下标从 1 开始)。
| 起点 | 覆盖下标 | 内容 | 是否单位 |
|---|---|---|---|
| 2 | 2–4 | abc | ✓ |
| 5 | 5–7 | abc | ✓ |
| 8 | 8–10 | abc | ✓ |
| 11 | 11–13 | abz | ✗ |
单位 2、5、8 连续(间隔恰好 3)→ 构成一个长度 3 的"连块"
整块取 k = 3 → a₃ = 2 分
切成 1 + 2 或 2 + 1 → a₁ + a₂ = 3 + 1 = 4 分
切成 1 + 1 + 1 → 3 × a₁ = 3 × 3 = 9 分 ← 最大
(注意块不能跨过 "abz",因为那不是 abc)
最优 9 分
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)
abz 不是单位,所以任何跨越它的块都不合法。这是本题复杂度能过关的核心原因。
若 n 也达到 10⁵,那么对每个 i 都要枚举 k = 1..O(i/3)
复杂度变成 O(m²/3) ≈ 3 × 10⁹
会超时
n 大时不可行
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⁵)。dp[i] 考虑"不用第 i 符"与"以 i 结尾取 3k 长的块"
枚举每段的切分与长度,递归求最大
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 前缀 DP | O(nm) | ✅ 稳过 |
| 搜索切分 | 指数级 | ❌ 不可行 |
第一行输入各 k 的分值,第二行输入字符串,程序会算出最大总分。
点按钮开始 →
#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; }
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 递增(题目没这个保证,必须都枚举)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 9 | 题面样例(切成三段 abc) |
3 | 6 | 两段 k=1 得 3+3=6,优于整段 k=2 的 1 |
1 | 5 | 恰好一个 abc 块 |
1 | 0 | 构不成 abc,得分 0 |
2 | 20 | 两个 k=1 的块,各得 10 |
2 | 20 | 同样切成两段更优(k=2 只给 1) |
dp[i] 必须能继承 dp[i−1]。a_k 不一定随 k 递增,必须枚举所有 k。dp 数组长度 m+1,分值数组长度 n+1。
✅ 约 200 万次操作,瞬间完成。本题的关键是"看数据范围定算法":n 小、m 大 → 内层枚举 n。
// 前缀 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
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 前缀 DP | dp[i] 表示前 i 位最优 | 所有"序列上选不重叠区间"的问题 |
| 提前 break | 不合法后更长区间也不合法 | 可行性具有单调性的枚举 |
| 看范围定算法 | 小维度内层、大维度外层 | 数据范围一大一小时的通法 |
n 只有 20,所以内层枚举 k 很轻松。如果 n 也放大到 10⁵,你会怎么优化?(提示:可以先把字符串切成若干"极大连块"(由连续 abc 组成的最长段),每个连块长度记作 L;在连块内部就变成"把 L 拆成若干份、使 Σ a[份大小] 最大"的完全背包问题,而连块之间互不影响。这样总复杂度由"所有连块长度的平方和"决定,在实践中通常远小于 m²。)