把 n 名同学分成若干组,组内 k 人得 a_k 分,求最大总分。
把 n 名同学划分成若干小组,每人必须属于某个组。若某个小组恰好 k 人,则该组积极度为 a_k。求所有划分方案中积极度之和的最大值。
dp[i] 表示"把 i 名同学分组能得到的最大积极度",转移就是枚举最后分出的一组有多少人:dp[i] = max(dp[i−k] + a_k)(k 从 1 到 i)。整数划分分割型 DP完全背包枚举组大小
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 a₁…aₙ |
| 输出 | 最大积极度之和 |
| 数据范围 | 1 ≤ n ≤ 1000 |
| 分值范围 | 0 ≤ aᵢ ≤ 10⁴ |
| 约束 | 每人属于恰好一个组;组大小可重复出现 |
dp[i] = 把 i 个人分组的最大总分,dp[0] = 0dp[i] = max(dp[i−k] + a[k]),k 遍历 1 ~ ia₁=1、a₂=5、a₃=6、a₄=3。
0 个人不需要分组
dp[0] = 0
只能分成 1 人组:dp[0] + a₁ = 0 + 1 = 1
dp[1] = 1
k = 1:一个 1 人组 → dp[1] + a₁ = 1 + 1 = 2
k = 2:一个 2 人组 → dp[0] + a₂ = 0 + 5 = 5
取最大 → 5
dp[2] = 5
k = 1:dp[2] + a₁ = 5 + 1 = 6
k = 2:dp[1] + a₂ = 1 + 5 = 6
k = 3:dp[0] + a₃ = 0 + 6 = 6
三种都是 6
dp[3] = 6
k = 1:dp[3] + 1 = 7
k = 2:dp[2] + 5 = 5 + 5 = 10
k = 3:dp[1] + 6 = 1 + 6 = 7
k = 4:dp[0] + 3 = 3
取最大 → 10
✅ dp[4] = 10
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| dp[i] | 0 | 1 | 5 | 6 | 10 |
| 最优方案 | — | 1 | 2 | 1+2 或 3 | 2+2 |
最优划分:2 + 2 → 5 + 5 = 10 ✓
2 + 1 + 1 = 7 这样的错误结果。读题时要抓住"每个小组恰好 k 人得 a_k 分",并没有说"组大小不能重复"。这组数据里 a₁ = 0,所以"单独成组"没有收益。
| i | dp[i] | 最优最后一组大小 | 说明 |
|---|---|---|---|
| 1 | 0 | 1 | a₁ = 0 |
| 2 | 2 | 2 | a₂ = 2 |
| 3 | 5 | 3 | a₃ = 5 |
| 4 | 6 | 4 | a₄ = 6 |
| 5 | 7 | 5 | max(dp[4]+0, dp[2]+a₃=2+5=7, a₅=4) = 7 |
| 6 | 10 | 3 + 3 | dp[3] + a₃ = 5 + 5 = 10 |
| 7 | 11 | 3 + 4 | dp[4] + a₃ = 6 + 5 = 11 |
| 8 | 12 | 2 + 3 + 3 | dp[5] + a₃ = 7 + 5 = 12 |
答案 12 ✓
dp[5] + a₃ = 7 + 5 = 12,即"先分 5 个人(最优 7 分),再补一个 3 人组(5 分)"。dp[5] = dp[2] + a₃ = 2 + 5 = 7,所以整体是"2 + 3 + 3"三组,得分 2 + 5 + 5 = 12 ✓。这种"从子问题拼出来"的过程正是 DP 的精髓。dp[i] 枚举最后一组大小 k,dp[i] = max(dp[i−k] + a[k])
a_k 并不是线性的,所以只能老老实实 DP 枚举。枚举 n 的所有整数分拆,逐一计算得分
2.4 × 10³¹——比宇宙原子数还多。而 DP 只需 10⁶ 次运算,这就是"用状态压缩掉重复子问题"的威力。| 方案 | 复杂度(n = 1000) | 可行性 |
|---|---|---|
| 整数划分 DP | 约 10⁶ | ✅ 瞬间 |
| 枚举分拆 | 指数/天文级 | ❌ 不可行 |
第一行输入 n,第二行输入各规模小组的积极度,程序会算出最大总和。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[1005], dp[1005]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); dp[0] = 0; // 0 个人得 0 分 for (int i = 1; i <= n; i++) { long long best = 0; for (int k = 1; k <= i; k++) { // 枚举"最后一组"的人数 best = max(best, dp[i - k] + a[k]); } dp[i] = best; } printf("%lld\n", dp[n]); return 0; }
best 初值取 0 就够?因为题目保证 a_i ≥ 0,所以"分成若干组"的总分一定 ≥ 0。a_i 可能为负,初值就要设成很小的数(如 -1e18),并且要想清楚"是否允许不分组"(题目要求每人必须分组,所以不允许)。初值的选取要结合题意,不能照抄模板。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dp[0] = 0 | 边界 | 0 个人的总分为 0 |
for (k = 1; k <= i; k++) | 枚举组大小 | 最后一组可以是 1 ~ i 人中的任意大小 |
dp[i - k] + a[k] | 转移 | 前 i−k 个人的最优 + 这一组的得分 |
best = max(best, ...) | 取最优 | 在所有分法中选最大的 |
k < i(会漏掉"整组就是 i 人"的情形)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 10 | 题面样例 1(2 + 2) |
8 | 12 | 题面样例 2(2 + 3 + 3) |
1 | 7 | 只分一组 |
3 | 0 | 所有分值都是 0 |
6 | 6 | 每种组都只值 1 分,分成 6 个单人组 |
6 | 100 | 整组 6 人最划算 |
k 要遍历到 i(包含"整组 i 人")。dp 数组 + 价值数组,都是 O(n)。
✅ 约 50 万次运算,瞬间完成。若 n 放大到 10⁵,就需要更高级的优化(本题不需要)。
// 整数划分型 DP 的通用骨架 dp[0] = 0; for (int i = 1; i <= n; i++) for (int k = 1; k <= i; k++) // 枚举"最后一块"的大小 dp[i] = max(dp[i], dp[i - k] + a[k]); // 与背包问题的对照 // - 本题:dp[i] 表示"凑出总量 i"的最优值,k 可重复使用 -> 完全背包 // - 若题目改成"每种组大小最多用一次" -> 0/1 背包(外层变成枚举物品) // 差别只在"循环顺序"和"物品是否可重复" // 完全背包(本题形式) for (int i = 1; i <= n; i++) for (int k = 1; k <= i; k++) dp[i] = max(dp[i], dp[i-k] + a[k]); // 类似题目 // - 把 n 拆成若干正整数之和,使某种收益最大 // - 找零钱问题(硬币面额可重复使用) // - 分段问题(每段长度有不同收益)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 整数划分 DP | 枚举"最后一块"的大小 | 所有"把 n 拆成若干份"的问题 |
| 完全背包 | 物品可重复使用 | 找零钱、分组、切分 |
| 0/1 vs 完全 | 看循环顺序与物品是否可重复 | 背包问题的关键区分点 |