GESP 题解库 / 6 级题解 / [GESP202509 六级] 划分字符串 · 第 6 / 27 题
GESP202509 六级 · P14075 · 中等

划分字符串

把字符串切成若干"字母不重复"的子串,使价值之和最大。

📊
n ≤ 10⁵
字符串长度
🔢
long long
价值范围
⚡
O(26n)
时间复杂度
🎯
DP + "长度≤26"关键观察
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定长度 n 的小写字母串 s,把它划分成若干子串,要求每个子串内的字母都不重复。给定价值数组 a₁…aₙ,表示长度为 i 的子串价值为 aᵢ。求划分后价值之和的最大值。

💡
人话翻译:这是"分割型 DP":dp[i] = 前 i 个字符能取得的最大价值,转移是枚举最后一段的长度:dp[i] = max(dp[i−len] + a[len])。
本量关键在于"len 最多只有 26"——因为小写字母只有 26 种,子串内字母不重复就意味着长度 ≤ 26。于是枚举量从 O(n) 降到 O(26)!

🔍 关键词提取

分割型 DP字母不重复抽屉原理O(26n)

已知条件

项目说明
输入第一行 n;第二行串 s;第三行 a₁…aₙ
输出最大价值之和
数据范围1 ≤ n ≤ 10⁵
价值范围1 ≤ aᵢ ≤ 10⁹
约束每个子串内每个字母至多出现一次

需要解决的问题

02
思维导图
整理解题思路的全貌
✂️ dp[i] = max(dp[i−len] + a[len])
🧠 状态定义
dp[i]:前 i 个字符的最大价值
dp[0] = 0
答案是 dp[n]
按前缀递推
🔁 转移
枚举最后一段的长度 len
要求 s[i−len .. i−1] 字母不重复
dp[i] = max(dp[i−len] + a[len])
取所有合法 len 的最大值
🔑 关键观察
字母只有 26 种
不重复 ⇒ 长度 ≤ 26
所以 len 只需枚举 1 ~ 26
复杂度降到 O(26n)
⚠️ 易错点
枚举 len 到 i(O(n²) 超时)
用 int(价值可达 10¹⁴)
重复检测写错(忘了提前退出)
dp[0] 未初始化
03
样例手算推导
两个样例的 dp 推演

🧮 样例 1:s = "street",a = [2,1,7,4,3,3]

a 的下标是"子串长度",所以 a₁=2、a₂=1、a₃=7…

1
dp[0] = 0

空串价值为 0

dp[0] = 0

2
dp[1](前缀 "s")

len = 1:子串 "s" 无重复 ✓

dp[1] = dp[0] + a₁ = 0 + 2 = 2

dp[1] = 2

3
dp[2](前缀 "st")

len = 1:"t" ✓ → dp[1] + a₁ = 2 + 2 = 4

len = 2:"st" ✓(s、t 不重复)→ dp[0] + a₂ = 0 + 1 = 1

取最大 → 4

dp[2] = 4

4
dp[3](前缀 "str")

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

5
dp[4](前缀 "stre")—— 出现重复!

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

6
dp[5](前缀 "stree")

len = 1:"e" ✓ → dp[4] + 2 = 11

len = 2:"ee" ✗ 出现重复,立即停止

所以不再考虑更长的 len(因为更长一定也含重复)

dp[5] = 11

dp[5] = 11

7
dp[6](完整串 "street")

len = 1:"t" ✓ → dp[5] + 2 = 13

len = 2:"et" ✓ → dp[4] + 1 = 10

len = 3:"eet" ✗ 停止

dp[6] = 13

✅ 答案 13

📊 dp 汇总

i0123456
前缀sststrstrestreestreet
dp[i]024791113

最优划分:str + e + e + t → 7 + 2 + 2 + 2 = 13 ✓

🔑
注意 "e + e" 这两段:它们是两个独立的子串,各自都只有 1 个字母,所以允许重复字母出现在不同子串里。题目只要求"子串内不重复",不是整个划分后不能有相同字母。

🧮 样例 2:s = "blossoms",a = [1,1,2,3,5,8,13,21]

这组数据的价值随长度增长得很快(像斐波那契),但因为有 "ss" 的重复,长段常常不可用。

i前缀dp[i]最优最后一段
0(空)0—
1b1"b"(长度 1,价值 1)
2bl2"l"
3blo3"o"
4blos4"s"
5bloss5"s"("ss" 重复,不能取长度 2)
6blosso6"o"
7blossom7"m"
8blossoms8"s"
1
为什么 dp[5] 只能加长度 1?

前缀是 "bloss",最后两个字符是 "ss"

len = 1:"s" ✓ → dp[4] + a₁ = 4 + 1 = 5

len = 2:"ss" ✗ 重复 → 停止枚举

所以 dp[5] = 5

dp[5] = 5

2
为什么最终是 8?

看起来 a₄ = 3、a₅ = 5、a₈ = 21 都很诱人

但因为 "ss" 的存在,任何跨越这两个 s 的段都非法

所以只能一段一段切(每段长度 1)

总价值 = 1 × 8 = 8

✅ 答案 8

答案 8 ✓

⚠️
这个样例很能说明"DP 必须老老实实枚举":a₈ = 21 看起来最大,但整个串 "blossoms" 含重复的 s,不能作为一整段。如果只贪心地"尽量取长段",就会出错。dp 的 max 会把所有合法长度都考虑进去。
04
解法对比
O(26n) DP vs O(n²) DP

⚔️ 解法对比

🟢 利用"长度 ≤ 26"优化(推荐) 推荐

枚举最后一段长度时,一旦出现重复字母就立即停止

  • 时间 O(26n) ≈ 2.6 × 10⁶
  • n = 10⁵ 时轻松通过
  • 代码 25 行
  • 空间 O(n)
💡
内层循环的写法:从 i 往前逐字符走,用 cnt[字符] 计数;一旦 cnt > 1 就 break。由于字母只有 26 种,这个循环最多跑 26 次。

🟠 朴素 O(n²) DP

对每个 i 枚举所有可能长度,用前缀和判断合法性

  • 时间 O(n²) = 10¹⁰
  • 必然超时
  • 只能通过 40% 的小数据
  • 逻辑正确但太慢
⚠️
关键差距:朴素做法忽略了"合法段长度天然 ≤ 26"这个事实,白白枚举了大量不可能的长度。竞赛中"从题目条件里抠出隐含上界"往往能把复杂度降一个量级。

📈 性能对比

方案运算量(n = 10⁵)可行性
长度≤26 优化约 2.6 × 10⁶✅ 稳过
朴素 O(n²) DP约 10¹⁰❌ 超时
05
算法流程图
分割型 DP:枚举长度直到出现重复
开始读入 n、串 s、价值数组 a;dp[0] = 0i 从 1 到 n清空计数数组 cnt;令 best = 负无穷len 从 1 开始递增(最多 26)加入字符 s[i−len] 后是否出现重复?是 ✓立即停止枚举 len否 ✗更新 best = max(best, dp[i−len] + a[len])dp[i] = best输出 dp[n]i 加 1 递推下一个前缀
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✂️ 最大划分价值

第一行输入字符串,第二行输入各长度的价值,程序会算出最大价值并展示 dp。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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 的初始化。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
6
street
2 1 7 4 3 3
13题面样例 1:str + e + e + t
8
blossoms
1 1 2 3 5 8 13 21
8题面样例 2(含 "ss" 重复)
1
a
5
5单字符
3
abc
1 10 100
100整串合法,取长度 3
3
aaa
1 10 100
3只能切成三个单字符:1+1+1 = 3
2
aa
100 100
200重复字母必须切分
✅
自查清单:① 内层限制 len ≤ 26 吗?② 出现重复立即 break 吗?③ 用 long long 吗?

🚨 易错点清单

⚠️
枚举所有长度:合法的段长天然 ≤ 26,不利用这点会退化成 O(n²)。
⚠️
用 int:价值可达 10¹⁴,需要 long long。
⚠️
初始值错:dp[0] 必须为 0,且内层 best 初值要足够小(用 -1 即可,因为价值非负)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(26n)
空间复杂度
O(n)
运算量
约 2.6 × 10⁶
关键
合法段长度 ≤ 26

时间怎么算的?

空间都用在哪?

dp 数组 + 字符串 + 价值数组。

✅ 约 260 万次操作,瞬间完成。注意:若字母表变成 52 种(大小写),上限变成 52,依然是 O(52n)。

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

🔗 常用技巧小抄

// 分割型 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(字母种数)
// - 数值范围小 -> 状态可枚举
// - 答案单调 -> 可以二分
// 这些"隐含上界"往往就是复杂度的突破口

// 类似题目
// - 把数组分成若干段使代价最小/最大
// - 每段有长度限制的分段问题

🌟 举一反三

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

能力点本题怎么用还能迁移到
分割型 DPdp[i] 枚举最后一段切分字符串/数组的所有分段问题
隐含上界字母不重复 ⇒ len ≤ 26利用题目条件降复杂度
单调性 break不合法后更长段必不合法双指针、滑动窗口类优化
🌟
思考题:如果题目把"小写字母"改成"至多 10 种字符",复杂度会变吗?(提示:会变,而且是变快——内层枚举上限从 26 降到 10,复杂度变成 O(10n)。这说明"字母表的种类数"直接决定内层循环的长度,所以看到"字符不重复"就要立刻想到"段长受限于字符种类数"。)