把字符串切成若干"字母不重复"的子串,使价值之和最大。
给定长度 n 的小写字母串 s,把它划分成若干子串,要求每个子串内的字母都不重复。给定价值数组 a₁…aₙ,表示长度为 i 的子串价值为 aᵢ。求划分后价值之和的最大值。
dp[i] = 前 i 个字符能取得的最大价值,转移是枚举最后一段的长度:dp[i] = max(dp[i−len] + a[len])。分割型 DP字母不重复抽屉原理O(26n)
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行串 s;第三行 a₁…aₙ |
| 输出 | 最大价值之和 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 价值范围 | 1 ≤ aᵢ ≤ 10⁹ |
| 约束 | 每个子串内每个字母至多出现一次 |
a 的下标是"子串长度",所以 a₁=2、a₂=1、a₃=7…
空串价值为 0
dp[0] = 0
len = 1:子串 "s" 无重复 ✓
dp[1] = dp[0] + a₁ = 0 + 2 = 2
dp[1] = 2
len = 1:"t" ✓ → dp[1] + a₁ = 2 + 2 = 4
len = 2:"st" ✓(s、t 不重复)→ dp[0] + a₂ = 0 + 1 = 1
取最大 → 4
dp[2] = 4
len = 1:"r" ✓ → dp[2] + 2 = 6
len = 2:"tr" ✓ → dp[1] + 1 = 3
len = 3:"str" ✓ → dp[0] + a₃ = 7
取最大 → 7
dp[3] = 7
len = 1:"e" ✓ → dp[3] + 2 = 9
len = 2:"re" ✓ → dp[2] + 1 = 5
len = 3:"tre" ✓ → dp[1] + a₃ = 2 + 7 = 9
len = 4:"stre" ✓ → dp[0] + a₄ = 4
取最大 → 9
dp[4] = 9
len = 1:"e" ✓ → dp[4] + 2 = 11
len = 2:"ee" ✗ 出现重复,立即停止
所以不再考虑更长的 len(因为更长一定也含重复)
dp[5] = 11
dp[5] = 11
len = 1:"t" ✓ → dp[5] + 2 = 13
len = 2:"et" ✓ → dp[4] + 1 = 10
len = 3:"eet" ✗ 停止
dp[6] = 13
✅ 答案 13
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 前缀 | s | st | str | stre | stree | street | |
| dp[i] | 0 | 2 | 4 | 7 | 9 | 11 | 13 |
最优划分:str + e + e + t → 7 + 2 + 2 + 2 = 13 ✓
这组数据的价值随长度增长得很快(像斐波那契),但因为有 "ss" 的重复,长段常常不可用。
| i | 前缀 | dp[i] | 最优最后一段 |
|---|---|---|---|
| 0 | (空) | 0 | — |
| 1 | b | 1 | "b"(长度 1,价值 1) |
| 2 | bl | 2 | "l" |
| 3 | blo | 3 | "o" |
| 4 | blos | 4 | "s" |
| 5 | bloss | 5 | "s"("ss" 重复,不能取长度 2) |
| 6 | blosso | 6 | "o" |
| 7 | blossom | 7 | "m" |
| 8 | blossoms | 8 | "s" |
前缀是 "bloss",最后两个字符是 "ss"
len = 1:"s" ✓ → dp[4] + a₁ = 4 + 1 = 5
len = 2:"ss" ✗ 重复 → 停止枚举
所以 dp[5] = 5
dp[5] = 5
看起来 a₄ = 3、a₅ = 5、a₈ = 21 都很诱人
但因为 "ss" 的存在,任何跨越这两个 s 的段都非法
所以只能一段一段切(每段长度 1)
总价值 = 1 × 8 = 8
✅ 答案 8
答案 8 ✓
枚举最后一段长度时,一旦出现重复字母就立即停止
i 往前逐字符走,用 cnt[字符] 计数;一旦 cnt > 1 就 break。由于字母只有 26 种,这个循环最多跑 26 次。对每个 i 枚举所有可能长度,用前缀和判断合法性
| 方案 | 运算量(n = 10⁵) | 可行性 |
|---|---|---|
| 长度≤26 优化 | 约 2.6 × 10⁶ | ✅ 稳过 |
| 朴素 O(n²) DP | 约 10¹⁰ | ❌ 超时 |
第一行输入字符串,第二行输入各长度的价值,程序会算出最大价值并展示 dp。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[100005], dp[100005]; char s[100005]; int main() { int n; scanf("%d", &n); scanf("%s", s + 1); // 1-based,方便用 dp[i] 表示"前 i 个字符" for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); dp[0] = 0; for (int i = 1; i <= n; i++) { int cnt[26] = {0}; // 本次枚举的字符计数 long long best = -1; // 从后往前扩展最后一段,长度最多 26 for (int len = 1; len <= i && len <= 26; len++) { int c = s[i - len + 1] - 'a'; cnt[c]++; if (cnt[c] > 1) break; // 出现重复,后面的更长段一定也不合法 best = max(best, dp[i - len] + a[len]); } dp[i] = best; } printf("%lld\n", dp[n]); return 0; }
break"?因为我们是从短的段往长的段扩展的:如果长度 len 的这一段已经含重复字母,那么长度 len+1 的段(在它前面再加一个字符)必然也含重复。所以后面的都不必再试。这个"单调性"正是循环能提前退出的依据,也是复杂度能降到 O(26n) 的关键。dp[0] = 0 必须初始化,它对应"整段就是一个子串"的情形。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
cnt[26] = {0} | 字符计数 | 每个 i 都重新清空 |
len <= 26 | 长度上界 | 字母只有 26 种,不重复则长度 ≤ 26 |
if (cnt[c] > 1) break; | 合法性判断 | 单调性:出现重复后更长段也必然重复 |
dp[i - len] + a[len] | 转移 | 最后一段 + 之前的最优 |
long long | 类型 | 价值可达 10¹⁴ |
i(O(n²) 超时,忘了长度 ≤ 26);② 用 int(n × aᵢ 可达 10¹⁴);③ 出现重复后没 break(虽然结果仍对,但复杂度退化);④ 忘了 dp[0] = 0 的初始化。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 13 | 题面样例 1:str + e + e + t |
8 | 8 | 题面样例 2(含 "ss" 重复) |
1 | 5 | 单字符 |
3 | 100 | 整串合法,取长度 3 |
3 | 3 | 只能切成三个单字符:1+1+1 = 3 |
2 | 200 | 重复字母必须切分 |
dp[0] 必须为 0,且内层 best 初值要足够小(用 -1 即可,因为价值非负)。dp 数组 + 字符串 + 价值数组。
✅ 约 260 万次操作,瞬间完成。注意:若字母表变成 52 种(大小写),上限变成 52,依然是 O(52n)。
// 分割型 DP 的通用骨架 dp[0] = 0; for (int i = 1; i <= n; i++) { for (int len = 1; len <= i && len <= 26; len++) { if (!合法(i - len + 1, i)) break; // 一旦不合法就退出 dp[i] = max(dp[i], dp[i - len] + a[len]); } } // 从题目条件里抠"隐含上界"的思路 // - 字母不重复 -> 长度 <= 26(字母种数) // - 数值范围小 -> 状态可枚举 // - 答案单调 -> 可以二分 // 这些"隐含上界"往往就是复杂度的突破口 // 类似题目 // - 把数组分成若干段使代价最小/最大 // - 每段有长度限制的分段问题
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 分割型 DP | dp[i] 枚举最后一段 | 切分字符串/数组的所有分段问题 |
| 隐含上界 | 字母不重复 ⇒ len ≤ 26 | 利用题目条件降复杂度 |
| 单调性 break | 不合法后更长段必不合法 | 双指针、滑动窗口类优化 |