学术
学会这个经典题型，六级通过率大大增加 —— GESP 六级经典套路题之「划分 DP」
黑大帅黑大帅 LV 8 SU @ 2026-1-19 21:22:26

学会这个经典题型，六级通过率大大增加 —— GESP 六级经典套路题之「划分 DP」

很多同学刷 GESP 六级时会有一种体验：题面千变万化，但最后“都在让你把东西切成一段一段”。
字符串切子串、数组分组、挑若干互不重叠片段计分……这些题的共同底层，几乎都能落到一个模型：划分型动态规划（划分 DP）。

这一篇推文用你给的材料做系统梳理，并把六级真题中最常见的三类“划分 DP 味道”串起来：你以后看到类似题，第一反应就能直接建模。

一、划分 DP 到底在做什么

一句话定义：
给定一个线性结构（数组/字符串/序列），把它切成若干个连续段，每段产生一个“贡献/代价”，整体要 最大化/最小化 目标。

划分 DP 的核心永远是两件事：

状态怎么定义（用什么维度描述“做到哪了”）
最后一刀在哪里切（枚举分割点，把大问题拆成小问题）

你给的材料非常关键：划分 DP 主要分两种套路。

二、套路 1：确定段数的划分（经典二维 DP）

这类题目会明确告诉你要切成 恰好 K 段（或隐含必须切 K 段），典型状态是二维：

1）状态定义

常用：

dp[i][j]

表示“前 $i$ 个元素，划分成 $j$ 段时的最优值”。

2）转移（枚举最后一段的起点）

$$dp_{i,j} = opt_{k < i} \{dp_{k - 1,j - 1} + cost(k + 1,i)\} $$

其中 $k$ 是上一段结束位置， $(k+1 \sim i)$ 是最后一段。

3）初始化、顺序、答案

初始化通常是 $dp[0][0]=0$ ，其余为 $\pm\infty$ （按 min/max）
计算顺序：i 从小到大，j 从 1 到 K
答案一般是 $dp[n][K]$

一句话记忆法：

“二维划分 = 前 i 个 + 切 j 段 + 枚举最后一段从哪来。”

三、套路 2：不确定段数的划分（经典一维 DP / 枚举最后一段）

更常见。题面不要求段数固定，而是“任意切，但要最优”。
这就是你给的通用模板：

1）状态

dp[i] = \text{前 } i \text{ 个元素切成若干段的最优值}

2）转移（枚举最后一段）

dp_{i} = opt_{k < i} \{dp_{k} + cost(k + 1,i)\}

并且必须满足最后一段合法（长度/字符唯一/结构匹配等约束）。

3）初始化

最小化： $dp[0]=0$ ，其余 $+\infty$
最大化： $dp[0]=0$ ，其余 $-\infty$

一句话记忆法：

“一维划分 = 只管前 i 最优，最后一段从 k+1 到 i。”

四、例题/真题实战

例题 1：真题 -「学习小组」—— 典型“一维划分段数不定 + 纯长度代价”

题目描述

班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 $k$ 名同学，则该学习小组的讨论积极度为 $a_k$ 。

给定讨论积极度 $a_1, a_2, \ldots, a_n$ ，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。

输入格式

第一行，一个正整数 $n$ ，表示班级人数。

第二行， $n$ 个非负整数 $a_1, a_2, \ldots, a_n$ ，表示不同人数学习小组的讨论积极度。

输出格式

输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。

输入 #1
4
1 5 6 3
输出 #1
10
说明/提示

对于 $40\%$ 的测试点，保证 $1\le n\le 10$ 。

对于所有测试点，保证 $1\le n\le 1000$ ， $0\le a_i\le 10^4$ 。

题眼：把 n 个同学分成若干组，组大小为 k 的积极度是 $a_k$ ，最大化总和。

这题看似“划分”，但注意：这里并没有“连续”的概念，因为同学本质是“无序集合”。
然而它依然是一个经典 DP：整数拆分/分组 DP。六级考它的目的就是看你能否把它抽象成“切段长度”。

1）识别信号

“划分为若干组”
“每组贡献只与人数 k 有关”
“总人数固定为 n，求最大”

这等价于：把整数 n 拆成若干正整数之和，每个部分 x 的贡献是 $a_x$ 。

2）标准建模（完全背包味道的一维 DP）

令 $dp[i]$ 表示凑到 i 个人时的最大积极度：

dp[i]=\max_{1\le k\le i}\{dp[i-k]+a_k\}

初始化 $dp[0]=0$ 。

3）这题在划分 DP 体系里的定位

它和“切字符串”不同点在于：

“段”不再对应“连续区间”，而是对应“组大小”
但转移形式仍然是“枚举最后一段/最后一组大小”

所以它训练的是：你能不能把题面语言翻译成「最后一组是多少」。

4）参考代码

#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1005],a[1005];
int main () {

	  cin >> n;
	  for (int i = 1; i <= n; i++) {
		  cin >> a[i];
	  }
	  dp[0] = 0;
	  for (int i = 1; i <= n; i++) {
		  dp[i] = -2e9;
		  int sum = 0;
		  for (int l = i; l > 0; l--) {
			  sum ++;
			  dp[i] = max(dp[i],dp[l - 1] + a[sum]);
		  }
	  }
	  cout << dp[n];
	  return 0;
}

例题 2：真题 -「划分字符串」—— 典型“一维划分 + 段合法性”

题目描述

小 A 有一个由 $n$ 个小写字母组成的字符串 $s$ 。他希望将 $s$ 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。

额外地，小 A 还给出了价值 $a_1,a_2,\ldots,a_n$ ，表示划分后长度为 $i$ 的子串价值为 $a_i$ 。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

输入格式

第一行，一个正整数 $n$ ，表示字符串的长度。

第二行，一个包含 $n$ 个小写字母的字符串 $s$ 。

第三行， $n$ 个正整数 $a_1,a_2,\ldots,a_n$ ，表示不同长度的子串价值。

输出格式

一行，一个整数，表示划分后子串价值之和的最大值。

输入 #1
6
street
2 1 7 4 3 3
输出 #1
13
数据范围

对于 $40\%$ 的测试点，保证 $1\le n\le 10^3$ 。

对于所有测试点，保证 $1\le n\le 10^5$ ， $1\le a_i\le 10^9$ 。

1）识别信号

“划分为若干子串”
“每段需要满足一个性质（字母不重复）”
“每段贡献只与段长相关（ $a_{len}$ ）”
“总体求最大”

这几句组合在一起，几乎可以直接判定：一维划分 DP。

2）标准建模

令 $dp[i]$ 表示前 $i$ 个字符的最大得分（1-indexed）：

$$dp_i = \max_{k < i 并且 seg(k+ 1 \sim i) 合法} \{ dp_k + a[i- k] \} $$

3）关键优化点（为什么能到 $10^5$ ）

段的合法性是“子串内无重复字符”。
对固定右端点 $i$ ，合法的左端点范围可以用“最近重复位置”维护：
用数组 last[26] 记录每个字母上一次出现位置，维护一个最左界 L，保证 $[L,i]$ 内无重复。

于是每个 i 的合法 k 只会落在 $k \in [L-1, i-1]$ 。

进一步怎么提速？常见方向有两类：

如果直接枚举所有 k，最坏还是 $O(26n)$ 到 $O(n\cdot \text{alphabet})$ 级别（这里字母表26）
若题目更大字母集，会引出“数据结构维护区间最值/单调队列/线段树”一类优化（六级通常不会压得太极限）

结论：本题是“划分 DP 的入门模板题”，重点在“把合法段判定塞进枚举 k 的范围”。

4）参考代码

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

const int N=200000+5, M=26;
int n;
ll a[N], dp[N];
string s;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        bool vis[M]={0};
        for(int j=i,lim=max(1,i-M+1); j>=lim; --j){
            int idx=s[j-1]-'a';
            if(vis[idx]) break;
            vis[idx]=1;
            int len=i-j+1;
            dp[i]=max(dp[i], dp[j-1]+a[len]);
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}

例题 3：真题 -「计算得分」—— 典型“划分 + 只给特定片段计分（模式串）”

题目描述

小杨想要计算由 $m$ 个小写字母组成的字符串的得分。

小杨设置了一个包含 $n$ 个正整数的计分序列 $A=[a_1,a_2,\ldots,a_n]$ ，如果字符串的一个子串由 $k(1\leq k \leq n)$ 个 $\texttt{abc}$ 首尾相接组成，那么能够得到分数 $a_k$ ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设，字符串 $\texttt{dabcabcabcabzabc}$ 的所有可能计分方式如下：

$\texttt{d+abc+abcabc+abz+abc}$ 或者 $\texttt{d+abcabc+abc+abz+abc}$ ，其中 $\texttt{d}$ 和 $\texttt{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$ 。

$\texttt{d+abc+abc+abc+abz+abc}$ ，总得分为 $a_1+a_1+a_1+a_1$ 。

$\texttt{d+abcabcabc+abz+abc}$ ，总得分为 $a_3+a_1$ 。

小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

第一行包含一个正整数 $n$ ，代表计分序列 $A$ 的长度。

第二行包含 $n$ 个正整数，代表计分序列 $A$ 。

第三行包含一个正整数 $m$ ，代表字符串的长度。

第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

输出一个整数，代表给定字符串的最大总得分。

输入 #1
3
3 1 2
13
dabcabcabcabz
输出 #1
9
样例解释

最优的计分方式为 $\texttt{d+abc+abc+abc+abz}$ ，总得分为 $a_1+a_1+a_1$ ，共 $9$ 分。

数据范围

子任务编号数据点占比 $n$ $m$ $a_i$ 特殊性质

$1$ $20\%$ $\le 20$ $\le 10^5$ $\le 1000$ 对于所有的 $i(1 \le i \le n)$ ，存在 $a_i \ge a_{i+1}$

$2$ $40\%$ $\le 3$

$3$ $\le 20$

对于全部数据，保证有 $1\leq n\leq 20$ ， $1\leq m\leq 10^5$ ， $1\leq a_i\leq 1000$ 。

子任务编号	数据点占比	$n$	$m$	$a_i$	特殊性质
$1$	$20\%$	$\le 20$	$\le 10^5$	$\le 1000$	对于所有的 $i(1 \le i \le n)$ ，存在 $a_i \ge a_{i+1}$
$2$	$40\%$	$\le 3$
$3$	$\le 20$

题眼：字符串里只有形如若干个 abc 首尾相接（即 abcabc...）的子串能计分，长度为 k 个 abc 的得分为 $a_k$ 。计分片段不能重叠，最大化总得分。

1）识别信号

“字符串的子串可以计分，但字符不能重复计算得分”
→ 本质是“选若干互不重叠片段”
“可计分片段结构固定（abc 重复）”
“最大总分”

这依然可以落到一维划分 DP：从左到右决定“这里是否结束一个计分段”。

2）标准建模方式（切分 + 跳过无用字符）

令 $dp[i]$ 为前 i 个字符的最大得分：

不选第 i 位作为计分段结尾：
$dp[i]=dp[i-1]$
若存在一个计分段以 i 结尾，并且该段恰好是 abc 重复 k 次（长度 $3k$ ），则：
$dp[i]=\max(dp[i],\ dp[i-3k]+a_k)$

关键在于：如何快速判断 $[i-3k+1,i]$ 是否为 abcabc...。

3）实现策略

预处理 good[i]：以 i 结尾的最长 abc 连续重复次数（或最长匹配长度），用线性扫描即可
然后对每个 i，枚举 k=1..good[i] 更新 dp

由于本题 $n\le 20$ ，但 $m\le 10^5$ ，a_i $\le 1000$ ，通常允许 $O(m\cdot n)$ 或 $O(m\cdot 20)$ 的转移。

这题的本质训练点：

“划分 DP 不一定每个字符都属于一段；可以用 dp[i]=dp[i-1] 表示‘我跳过它’，再在某些位置‘接上一段计分段’。”

4）参考代码


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

const int N = 100000 + 10;

ll dp[N], a[N];
string s;

bool chk(int p){ 
	return s[p] == 'a' && s[p + 1] == 'b' && s[p + 2] == 'c';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	int m; cin >> m;
	cin >> s;
	
	s = " " + s; 
	for (int i = 1; i <= m; i++) dp[i] = 0;
	
	for (int i = 3; i <= m; i++) {
		dp[i] = dp[i - 1];
		
		for (int j = 1; j <= n; j++) {
			int p = i - 3 * j + 1;
			if (p < 1) break;
			
			if (!chk(p)) break; // 只要断了，后面更长的 j 也不可能成立
			
			dp[i] = max(dp[i], dp[i - 3 * j] + a[j]);
		}
	}
	
	cout << dp[m];
	return 0;
}

例题5-数列分组

题目描述

有一个 $n$ 长正整数序列 $A = a_1,...,a_n$ ，现在想将 $A$ 拆分成 $k$ 个连续的组，其中每一组的得分是该组最大值与最小值的差。

请你计算合法拆分方法下，最大总得分的值。

【例子】例如对于 $A = 1,3,4,1,2$ 与 $k = 2$ ，有如下 $4$ 种方法：。

$|\ 1\ |\ 3,4,1,2 \ |$ ，得到 $0 + 3 = 3$ 分。

$|\ 1,3\ |\ 4,1,2 \ |$ ，得到 $2 + 3 = 5$ 分。

$|\ 1,3,4\ |\ 1,2 \ |$ ，得到 $3 + 1 = 4$ 分。

$|\ 1,3,4,1\ |\ 2 \ |$ ，得到 $3 + 0 = 3$ 分。

于是最大总得分为 $5$ 。

输入格式

第一行两个正整数 $n,k$ 。

第二行 $n$ 个正整数 $a_1,...,a_n$ 。

输出格式

一个整数表示结果。

输入 #1
5 2
1 3 4 1 2
输出 #1
5
说明/提示

对于 $50\%$ 的数据： $1 \leq n \leq 15$ 。

对于 $100\%$ 的数据： $1 \leq k \leq n \leq 10^2$ ， $1 \leq a_i \leq 10^9$ 。

1）识别信号

“拆分成 k 个连续的组”
典型关键词：连续划分 + 段数固定 ⇒ 直接锁定 确定段数的划分 DP（二维 DP）。
“每组得分是该组 最大值与最小值的差”
段代价/段贡献是一个 区间函数： $\mathrm{cost}(l,r)=\max_{l..r}a-\min_{l..r}a$ 。
“求最大总得分”
⇒ opt = max。

结论：这是 固定段数的划分 DP（dp[i][j]）+ 区间代价 cost(l,r) 的标准模型。

2）建模方式

2.1 状态定义（固定段数模板）

令：

$$dp[i][j] = \text{把前 } i \text{ 个数划分成 } j \text{ 段时的最大总得分} $$

其中 $1\le j\le k,\ 1\le i\le n$ 。

2.2 转移方程（枚举最后一段起点）

最后一段是 $(t+1..i)$ ，则：

$$dp[i][j] = \max_{t\in[j-1,\,i-1]}\Big( dp[t][j-1] + cost(t+1,i) \Big) $$

其中：

$$cost(l,r)=\max_{l\le x\le r}a_x-\min_{l\le x\le r}a_x $$

2.3 初始化

$dp[0][0]=0$
其它不合法状态设为 $-\infty$ （或一个足够小的负数）
最终答案： $dp[n][k]$

3）关键优化点（在本题数据范围下怎么做最合理）

题目给到： $n\le 100$ 。这意味着：

朴素三层：
$i$ （1..n）× $j$ （1..k）× $t$ （枚举切点） ⇒ $O(n^3)$ 上限约 $10^6$ ，本身就能过。
真正需要注意的是：cost(l,r) 的计算如果你每次都扫描区间，会把整体搞成 $O(n^4)$ 。

4）参考代码

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

const int N = 105;
const ll neg = -(1LL << 60);

int n, k;
ll dp[N][N], a[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= k; j++) dp[i][j] = neg;
	}
	dp[0][0] = 0;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		
		for (int j = 1; j <= min(i, k); j++) {
			ll mx = -(1LL << 60), mn = (1LL << 60);
			
			for (int p = i; p >= 1; p--) {
				mx = max(mx, a[p]);
				mn = min(mn, a[p]);
				
				if (dp[p - 1][j - 1] == neg) continue;
				
				dp[i][j] = max(dp[i][j], dp[p - 1][j - 1] + (mx - mn));
			}
		}
	}
	
	cout << dp[n][k];
	return 0;
}

五、总结

做题时可以用下面这套“扫描题面关键词”的方法快速归类：

1）看有没有“切成若干段/若干组/若干子串”

有：先假设是划分 DP。

2）看段数是否固定

固定 K 段：优先考虑 $dp[i][j]$
不固定：优先考虑 $dp[i]$

3）看每段的价值怎么给

只和长度有关：转移里通常是 $+a_{len}$
和段内性质有关：需要先做“段合法性判定/预处理”
只有特定模式段能得分：通常出现 “跳过 dp[i-1] + 贴一段”

4）看数据范围决定你要不要优化

$n\le 1000$ ：暴力枚举 k 多半可过
$n\le 10^5$ ：必须想办法缩小 k 的枚举范围（双指针/last 数组/数据结构）

六、题外话

当数据范围变大时，划分 DP 的优化通常沿着两条主线走：

缩小候选切点集合（利用单调性/约束让合法 k 变成区间，双指针/前缀处理）；

把“枚举 k”变成“数据结构查询/数学优化”（Fenwick/线段树、分治优化、Knuth、斜率优化等）这篇文章只是介绍或者入门，不再具体的阐述了，后续章节再来详细介绍这类问题的优化问题，个人认为优化，其实是一个单独的问题，只是一个题目把这两种问题结合到了一个题目上。

目前还没有评论...