ARTICLE · 1357138
GESP 2025年9月 真题题解 | 划分字符串(动态规划)
小 A 有一个由 n 个小写字母组成的字符串 s。他希望将 s 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。
额外地，小 A 还给出了价值 a₁,a₂,…,aₙ，表示划分后长度为 i 的子串价值为 aᵢ。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？
street
2 1 7 4 3 3
blossoms
1 1 2 3 5 8 13 21
这题光看代码容易绕进去，先找个生活里的比方，比方对了，代码就是照着抄。
轮到 GESP 2025年9月 的动态规划题了。这题在考场上属于「必须拿分」那一档，下面按上课的顺序讲：先看什么、再算什么、最后怎么验。
题目：划分字符串
场次：2025年9月 六级｜难度：六级
知识点：线性动态规划
链接：https://www.acgo.cn/problemset/info/95217
小 A 有一个由 n 个小写字母组成的字符串 s。他希望将 s 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。 额外地，小 A 还给出了价值 a₁,a₂,…,aₙ，表示划分后长度为 i 的子串价值为 aᵢ。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？
一句话概括：用线性动态规划把题目要求原样翻译成代码，属于考场上必须拿满分的题。
前提一，容器够不够大。题干没直接写范围，但参考代码里用了 long long，说明中间结果会超过 21 亿——照抄类型就不会错。
前提二，两头有没有照顾到。数据从 1 开始编号，读入和循环都从 1 起，a[0] 留空不用，能省掉大量 ±1 的换算。
前提三，交出去的样子对不对。第三件，最后注意输出格式。题目要几行就几行，行内空格几个就是几个，行末的换行别丢——算法对了格式错了，一样判错，这分丢得最冤。
先说这个比方。DP 像记流水账：每一笔都记下来，算下一笔的时候直接查前面记好的，不用从头重算。账本怎么设计（状态定义）决定了后面好不好算。
把比方里的动作换成代码里的语句，思路就完整了。
比方和代码是一一对应的：比方里先说清「有几样东西」，对应代码里的变量；比方里「一个一个过」，对应那个循环。
建议先自己写二十分钟，卡住了再看。对着抄一遍的效果，比不上自己错一遍。
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
char s[N];
int a[N];
long long f[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 遍历
for (int i = 1; i <= n; i++) { // 遍历
int mask = 0; // 初始化
for (int j = i; j; j--) { // 遍历
int cur = 1 << (s[j] - 'a');
if (mask & cur) break; // 判断
mask |= cur;
f[i] = max(f[i], f[j - 1] + a[i - j + 1]);
}
}
printf("%lld\n", f[n]);
return 0;
}
代码在上面，这里只挑最关键的两段讲，其他都是顺手写的。
第一段，把数据读进来。
scanf("%s", s + 1);
读入这段只要盯一件事：变量类型装不装得下。其他都可以照抄。
第二段，核心处理。
for (int i = 1; i <= n; i++) {
int mask = 0;
for (int j = i; j; j--) {
int cur = 1 << (s[j] - 'a');
if (mask & cur) break;
mask |= cur;
f[i] = max(f[i], f[j - 1] + a[i - j + 1]);
}
// …（这段后面还有，见上面的完整代码）
这段是整道题唯一需要想的地方，也是动态规划的落点。看循环时只问三句：从哪开始、到哪结束、每次加几。三句都对，这段就没错。
代码写完不算完，得验。验也有顺序，从样例开始。
样例输入
street
2 1 7 4 3 3
样例输出
按这个顺序走一遍，跟上面那个比方对上：
- 跑题目给的样例，输出和样例逐字符一致，包括空格和换行。
- 试最小的输入，只给一个数、只给一行，程序不崩也不越界。
- 试空串和单字符，不越界，输出不为空。
- 看最后一行，结尾有换行，不多输出空行。
- 跑完剩下 1 组样例，全部对上再提交，别只看第一组。
题目还有 1 组样例，全部跑通再提交。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 递归层数爆栈 | 链状数据直接递归到 n 层 | 改显式栈，或把递归改成从底往上推 |
| 累加结果溢出 | int sum = 0; | long long 声明累加变量 |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
最后收个尾，三句话说完这题。
- 这题考的：线性动态规划——把题目条件一句一句翻译成代码，不添不减。
- 要记住的：先把
dp[i]的含义写成一句人话，比如「前 i 个物品的最优值」，定义错了后面全白写。 - 下一步：拿同场次另一道题练手，换题型不换节奏，手感就稳了。
这题就讲到这。同一场次的题我会接着更，跟着刷完一整场，你对这个级别的题感就出来了。
- 本文属于《GESP 真题题解》系列，第 79 篇，真题按年份持续补齐，每篇都带完整可编译代码，题号可在 ACGO 直接提交验证。
- 还没动笔的话，先自己写一遍再回来看踩坑总结，比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注，更新会第一时间推送。
- 本系列合集目录（按年份/组别排序）
GESP 的坑多半在边界和读题上。这道动态规划题把该注意的点都列在上面的表里了，提交前逐条过一遍。
今天想问你：你在考场上遇到这题会先写暴力再优化，还是直接上正解？说说你的策略。
把这篇转给一起刷题的同学，两个人对着讲一遍思路，比一个人看三遍都管用。关注本号不迷路。
真题代码包和更新排期都放在后台了，回复 “资料” 两个字自取。
本篇编号 GESP-029（公众号 MP-029）。完整目录与更多题解见博客专栏（公众号菜单「历史文章」）。
