把组内极差抽出来(Q(m) − P(m)),其余部分用 DP 求 Σa_k。
把 n 名同学划分成若干个学习小组,每人恰好属于一个组。若一个组恰好包含 k 名同学,则它的基础讨论积极度为 a_k,综合讨论积极度为
a_k + (组内最大的 c − 组内最小的 c)
给定 a₁, a₂, …, a_n 与每人的 cᵢ,求所有划分方案中综合积极度之和的最大值。
≥ 2 的小组共有 m 个,那么 Σ(组内极差) 的最大值只取决于 m:Σ(极差) ≤ Q(m) − P(m),其中 Q(m) 是最大的 m 个 c 之和、P(m) 是最小的 m 个 c 之和。Σa_k 只要做一个"组数 × 总人数"的 DP 就行。划分型问题极差可分离排序引理分组 DPO(n³)
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个 cᵢ;第三行 n 个 aᵢ |
| 输出 | 综合积极度之和的最大值 |
| 数据范围 | 1 ≤ n ≤ 300 |
| 数值范围 | 0 ≤ cᵢ ≤ 10⁴,0 ≤ aᵢ ≤ 10⁴ |
| 部分分 | 40% 的测试点保证 cᵢ = 0 |
| 组的形态 | 人数 = 组大小 k,贡献查 a_k |
Q(m) − P(m)?Σ(极差) = Σ(各组最大值) − Σ(各组最小值),前者最大就是"最大的 m 个 c 之和",后者最小就是"最小的 m 个 c 之和",且两者可以同时取到k = 1,组内最大 = 组内最小,极差恒为 0,所以只贡献 a₁n³/2 ≈ 1.35 × 10⁷,非常轻松c = [2, 1, 3, 2],a = [1, 5, 6, 3](即 a₁=1, a₂=5, a₃=6, a₄=3)。排序后 c = [1, 2, 2, 3]。
| 划分方案 | 各组的 (a_k + 极差) | 总和 |
|---|---|---|
| 4 个单人组 | 1 + 1 + 1 + 1(极差全为 0) | 4 |
| 一个 2 人组 + 2 个单人组 | (5 + 1) + 1 + 1 | 8 |
| 两个 2 人组(最优) | (5 + 1) + (5 + 1) | 12 |
| 一个 3 人组 + 1 个单人组 | (6 + 2) + 1 | 9 |
| 一个 4 人组 | 3 + 2 | 5 |
组一:同学 1(c=2)与同学 2(c=1)→ 5 + (2 − 1) = 6
组二:同学 3(c=3)与同学 4(c=2)→ 5 + (3 − 2) = 6
合计 12
✅ 12
两个组都是 2 人,所以 m = 2、S = 4
dp[2][4] = a₂ + a₂ = 5 + 5 = 10
Q(2) = 3 + 2 = 5(最大的 2 个 c)
P(2) = 1 + 2 = 3(最小的 2 个 c)
极差贡献 = 5 − 3 = 2
单人组 (n − S) = 0 个
总候选值 = 10 + 0 + 2 = 12
✅ 与暴力枚举一致
Q(2) − P(2) = 5 − 3 = 2。这不是巧合——把"每组一个最大值、每组一个最小值"全部拆开再相加,就得到"前 m 大之和 − 前 m 小之和"。c = [1, 3, 2, 4, 3, 5, 4, 6],a = [0, 2, 5, 6, 4, 3, 3, 4]。排序后 c = [1, 2, 3, 3, 4, 4, 5, 6]。
最优取 m = 3(3 个"人数 ≥ 2 的组")、S = 8(没有单人组)
组大小为 3、3、2
dp[3][8] = a₃ + a₃ + a₂ = 5 + 5 + 2 = 12
Q(3) = 6 + 5 + 4 = 15(最大的 3 个 c)
P(3) = 1 + 2 + 3 = 6(最小的 3 个 c)
极差贡献 = 15 − 6 = 9
总候选值 = 12 + (8 − 8) × a₁ + 9 = 21
✅ 21
组一:同学 1、2、4(c = 1, 3, 4)→ 5 + (4 − 1) = 8
组二:同学 3、6、7(c = 2, 5, 4)→ 5 + (5 − 2) = 8
组三:同学 5、8(c = 3, 6)→ 2 + (6 − 3) = 5
合计 8 + 8 + 5 = 21
注意"最大值"分别是 4、5、6(正好是最大的 3 个 c)
"最小值"分别是 1、2、3(正好是最小的 3 个 c)
✅ 21
| 方案 | 分组(按排序后的值) | 各组贡献 | 总和 |
|---|---|---|---|
| 连续区间 DP | [1, 2, 3]、[3, 4]、[4, 5, 6] | (5 + 2) + (2 + 1) + (5 + 2) | 17 |
| 正解(排序引理 + DP) | [1, 3, 4]、[2, 4, 5]、[3, 6] | (5 + 3) + (5 + 3) + (2 + 3) | 21 |
极差部分用 Q(m) − P(m) 抽干,Σa_k 部分用 dp[m][S] 求最大
Σ(极差) 只跟"有几个 ≥2 人的组"有关,最大值就是 Q(m) − P(m);② Σa_k 只跟"组数 + 各组人数"有关,用 DP 求最大。把 c 排序后,令每一组是排序数组上连续的一段
| 方案 | 复杂度 | 样例 2 的结果 |
|---|---|---|
| 排序引理 + DP | O(n³) ≈ 1.35 × 10⁷ | ✅ 21 |
| 连续区间 DP | O(n²) | ❌ 17 |
| 暴力枚举所有划分 | 指数级(Bell 数) | ❌ n = 300 完全不可行 |
三行输入:n / 每人的 cᵢ / 每个组大小的 aᵢ。程序会跑"排序引理 + DP",并同时显示错解(连续区间 DP)的结果作对照。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 305; const ll NEG = -(1LL << 60); int n; ll c[MAXN], a[MAXN]; ll pre[MAXN]; // pre[i]:排序后前 i 个 c 之和 ll dp[155][MAXN]; // dp[m][S]:恰好 m 个"人数>=2 的组"、总人数 S 时 Σa_k 最大 int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &c[i]); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); // 排序 + 前缀和:之后可以 O(1) 取"最小的 m 个 c 之和"与"最大的 m 个 c 之和" sort(c + 1, c + n + 1); for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i]; int maxm = n / 2; // "人数>=2 的组"最多 n/2 个 for (int m = 0; m <= maxm; m++) for (int S = 0; S <= n; S++) dp[m][S] = NEG; dp[0][0] = 0; for (int m = 1; m <= maxm; m++) for (int S = 2 * m; S <= n; S++) for (int k = 2; k <= S; k++) if (dp[m - 1][S - k] != NEG) dp[m][S] = max(dp[m][S], dp[m - 1][S - k] + a[k]); ll ans = 1LL * n * a[1]; // m = 0:全员单人组 for (int m = 1; m <= maxm; m++) for (int S = 2 * m; S <= n; S++) { if (dp[m][S] == NEG) continue; ll P = pre[m]; // 最小的 m 个 c 之和 ll Q = pre[n] - pre[n - m]; // 最大的 m 个 c 之和 ll val = dp[m][S] + 1LL * (n - S) * a[1] + Q - P; ans = max(ans, val); } printf("%lld\n", ans); return 0; }
Q − P?因为 Σ(组内极差) = Σ(各组最大值) − Σ(各组最小值)。Σ(最大值) ≤ Q(m);同理 Σ(最小值) ≥ P(m),于是 Σ(极差) ≤ Q(m) − P(m)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
sort(c + 1, c + n + 1); | 排序 | 排序后才能 O(1) 取前 m 小 / 前 m 大 |
pre[i] = pre[i-1] + c[i]; | 前缀和 | Q(m) = pre[n] − pre[n−m] |
dp[0][0] = 0; | DP 边界 | 0 个组、0 人时 Σa_k = 0 |
for (k = 2; k <= S; k++) | 转移 | 组大小至少 2(单人组单独用 a₁ 算) |
ans = 1LL * n * a[1]; | m = 0 的情形 | 全员单人组:极差全 0,共 n·a₁ |
val = dp[m][S] + (n−S)·a₁ + Q − P; | 合并 | 三块相加:Σa_k + 单人组贡献 + 极差贡献 |
Q + P;③ m = 0 没考虑(全单人组,答案是 n·a₁);④ 给单人组也算极差(应为 0);⑤ dp 数组第二维开小(S 要到 n,第一维要到 n/2)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 12 | 题面样例 1 |
8 | 21 | 题面样例 2(连续区间 DP 只会得 17) |
1 | 7 | n = 1:只能单人组,贡献 a₁ |
2 | 5 | 两人同组(a₂ = 5)优于两个单人组(2) |
3 | 100 | c 全为 0 → 极差为 0,只看 a_k |
4 | 4 | 全同值:极差恒 0,拆成全单人组最优 |
Q − P 吗?③ 考虑到 m = 0 了吗?④ 组大小从 2 开始枚举了吗?Q(m) − P(m),不是 +。n · a₁,必须参与取最大。a₁。dp 需 [n/2 + 1][n + 1]。dp 表大小 (n/2 + 1) × (n + 1) ≈ 151 × 301 ≈ 4.5 × 10⁴ 个 long long,约 360 KB;另有 c、a、pre 三个长度 n 的数组。
✅ 千万级操作,C++ 只需几十毫秒。n ≤ 300 这个规模,正是为"排序 + O(n³) 划分 DP"准备的。
// 学习小组:两步分离的通用套路 // (1) 极差部分:把它"抽干"成只跟组数 m 有关的量 // 设人数 >= 2 的组共有 m 个 // Σ(组内极差) 的最大值 = Q(m) - P(m) // Q(m) = 最大的 m 个 c 之和 // P(m) = 最小的 m 个 c 之和 // 理由:让最大的 m 个 c 各当一个组的 max、最小的 m 个 c 各当一个组的 min, // 剩下的元素塞进任意组都不改变 max / min // (2) Σa_k 部分:分组 DP // dp[m][S] = 恰好 m 个"人数 >= 2 的组"、总人数 S 时 Σa_k 的最大值 // 转移:dp[m][S] = max over k >= 2 of ( dp[m-1][S-k] + a_k ) // 含义:最后一个组放 k 个人,剩下 m-1 个组占 S-k 人 // (3) 合并:剩下的 (n - S) 人各自单独成组,每组只贡献 a_1(极差为 0) // ans = max over (m, S) of ( dp[m][S] + (n - S) * a[1] + Q(m) - P(m) ) // 别忘了 m = 0 的情况:ans 初始化为 n * a[1] // (4) 千万不要用"排序后连续区间 DP" // 那强行要求同组在排序数组上连续,会把跨组的更优搭配排除掉 // 本题样例 2:连续区间 DP = 17,正确答案 = 21
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 极差可分离 | 把 Σ(max−min) 化成 Q(m) − P(m) | 和式中的 max / min 只取决于"选了几个极值" |
| 排序 + 前缀和 | O(1) 取"前 m 小 / 前 m 大"之和 | 任何"取 k 个最小 / 最大"的题 |
| 分组 DP | dp[m][S] 记录"组数 + 总人数" | 装箱、划分、凑数类问题的建模 |
| 枚举 (m, S) 合并 | 把两块独立最优值相加 | 先分离、再合并的优化思路 |
a_k + 组内最大 c(只加最大值、不加最小值),排序引理还好用吗?(提示:好用。Σ(组内最大) ≤ Q(m),而且取"最大的 m 个 c 当各组最大值"就能取到等号,所以极差项换成 Q(m) 即可,DP 部分完全不用改。这类题的通用套路是:只要"组的额外贡献"只依赖组内的极值,就能把它抽出来变成"前 m 大 / 前 m 小"的组合问题。)