GESP 题解库 / 6 级题解 / [GESP202609 六级] 数组划分 · 第 26 / 27 题
GESP202609 六级 · · 中等

数组划分

把数组划分成若干连续子段,使各段和的平方之和最小。

📊
n ≤ 2000
数组长度
🔢
long long
结果范围
⚡
O(n²)
时间复杂度
🎯
前缀和 + 区间 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

把数组 A 划分为若干非空连续子段。一个子段的偏差值是段内元素和的平方;整个划分的偏差值是各段偏差值之和。求最小的偏差值。

💡
人话翻译:标准的"分段型 DP"。设 dp[i] = 前 i 个数划分后的最小偏差值。
枚举最后一段的起点 j:dp[i] = min(dp[j] + (pre[i] − pre[j])²),其中 pre 是前缀和。
n ≤ 2000,O(n²) = 4 × 10⁶,完全可行。

🔍 关键词提取

分段型 DP前缀和平方偏差O(n²)

已知条件

项目说明
输入第一行 n;第二行 n 个整数 aᵢ
输出最小偏差值
数据范围1 ≤ n ≤ 2000
数值范围−100 ≤ aᵢ ≤ 100
段的性质非空、连续

需要解决的问题

02
思维导图
整理解题思路的全貌
✂️ dp[i] = min(dp[j] + (pre[i] − pre[j])²)
🧠 状态
dp[i]:前 i 个数的最小偏差
dp[0] = 0
答案 = dp[n]
按前缀长度递推
🔁 转移
枚举最后一段起点 j(0 ≤ j < i)
段和 = pre[i] − pre[j]
代价 = 段和的平方
dp[i] = min(dp[j] + 代价)
📐 为什么"段和"要平方
平方对大段惩罚更重
所以倾向拆细
但负数会让"拆细"不一定最优
必须 DP 枚举
⚠️ 易错点
段和用 int(可达 2000 × 100 = 2 × 10⁵,平方后 4 × 10¹⁰)
j 的枚举范围写错
忘记 dp[0] = 0
把"连续"理解成"任意"
03
样例手算推导
两个样例的完整推演

🧮 样例 1:A = [1, 2, −3, 4],答案 6

先算前缀和:0、1、3、0、4。

划分方案各段和偏差值
[1 2 −3 4]416
[1 2 −3][4]0, 40 + 16 = 16
[1][2 −3 4]1, 31 + 9 = 10
[1 2][−3 4]3, 19 + 1 = 10
[1][2][−3 4]1, 2, 11 + 4 + 1 = 6
[1][2][−3][4]1, 2, −3, 41 + 4 + 9 + 16 = 30

最小偏差值 6 ✓

1
DP 逐步计算

dp[0] = 0

dp[1] = dp[0] + (1)² = 1

dp[2] = min(dp[1] + (2)², dp[0] + (3)²) = min(5, 9) = 5

dp[3] = min(dp[2] + (−3)², dp[1] + (−2)², dp[0] + 0²)

= min(5 + 9, 1 + 4, 0) = min(14, 5, 0) = 0

dp[4] = min(dp[3] + 4², dp[2] + 1², dp[1] + 3², dp[0] + 4²)

= min(16, 6, 10, 16) = 6

✅ dp[4] = 6

🔑
注意 dp[3] = 0 这一步:前三项 1 + 2 + (−3) = 0,整段作为一段的偏差是 0² = 0——这是"负数让段和归零"的典型情形。
然后 dp[4] 从 dp[2] + 1² = 5 + 1 = 6 得到,对应划分 [1][2][−3 4]。

🧮 样例 2:A = [−1, −1, 4, −5, −1, 4],答案 0

这组数据的总和恰好是 0,所以"整段不切"就能拿到 0 分。

1
验证总和

(−1) + (−1) + 4 + (−5) + (−1) + 4

= −1 − 1 + 4 − 5 − 1 + 4

= 0

所以整段偏差 = 0² = 0

✅ 答案 0

2
DP 也会得到 0

dp[6] 会考虑 j = 0 的情况

即整段作为最后一段:dp[0] + (pre[6] − pre[0])² = 0

而偏差值不可能为负(平方和 ≥ 0)

所以 0 就是最小值

✅ 下界达到

📊 一个重要观察

因为偏差值是平方和,所以永远 ≥ 0。因此一旦能凑出"所有段和都为 0",就得到了理论最小值 0。

⚠️
但不要因此就写"贪心拆零":本题数据里有负数,"段和为零"未必能通过简单的贪心达成,而且一般情况下最优解也不是"全拆成零和段"。
老老实实写 O(n²) 的 DP 最稳妥——n ≤ 2000 的规模就是为 O(n²) 设计的。
04
解法对比
O(n²) DP vs 贪心/搜索

⚔️ 解法对比

🟢 区间划分 DP(推荐) 推荐

dp[i] 枚举最后一段起点 j,用前缀和 O(1) 取段和

  • 时间 O(n²) = 4 × 10⁶
  • 代码 12 行
  • 空间 O(n)
  • 对负数同样正确
💡
核心两行:for (j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + (pre[i]-pre[j])*(pre[i]-pre[j]));注意用 long long,因为段和的平方可达 4 × 10¹⁰。

🟠 贪心:遇到某处就切

按"段和尽量接近 0"之类规则贪心切分

  • 看起来合理
  • 但有反例(负数的存在使局部最优≠全局最优)
  • 无正确性保证
  • 不建议
⚠️
为什么不能贪心:平方函数是凸的,"拆细"和"合并"的收益取决于两侧的具体数值,不能只靠局部判断。
例如样例 1 里 1+2+(−3) = 0,合起来不花代价,但如果贪心一路拆开反而更贵(30 > 6)。

📈 性能对比

方案复杂度正确性
划分 DPO(n²)✅ 最优
贪心切分O(n)❌ 有反例
05
算法流程图
枚举最后一段起点递推
开始读入 n 和数组 A;计算前缀和 pre[0..n]dp[0] = 0,dp[1..n] = 正无穷i 从 1 遍历到 nj 从 0 遍历到 i − 1(枚举最后一段的起点)seg = pre[i] − pre[j];dp[i] = min(dp[i], dp[j] + seg × seg)i 是否已经到 n?输出 dp[n]i 加 1 递推下一个前缀
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✂️ 最小偏差值

输入数组,程序会算出最小偏差值并给出最优划分方案。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

long long a[2005], pre[2005], dp[2005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        pre[i] = pre[i - 1] + a[i];        // 前缀和
    }

    for (int i = 1; i <= n; i++) dp[i] = (long long)4e18;
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {       // 枚举最后一段 [j+1, i]
            long long seg = pre[i] - pre[j]; // 该段之和
            dp[i] = min(dp[i], dp[j] + seg * seg);
        }
    }

    printf("%lld\n", dp[n]);
    return 0;
}
🔑
为什么必须用 long long?段和最大约 2000 × 100 = 2 × 10⁵,平方后是 4 × 10¹⁰——远超 int 上限(约 2.1 × 10⁹)。
而总偏差值还要把多段相加,所以必须用 64 位整数。这是本题最容易"看起来对但过不了"的地方。

📖 关键几行怎么看

代码作用为什么这样写
pre[i] = pre[i-1] + a[i]前缀和让段和 O(1) 求出
for (j = 0; j < i; j++)枚举起点最后一段是 [j+1, i]
seg = pre[i] - pre[j]段和前缀和之差
dp[j] + seg * seg转移前缀最优 + 最后一段偏差
long long类型seg² 可达 4 × 10¹⁰
⚠️
四个坑:① 用 int(平方会溢出);② j 的枚举范围写成 1 ≤ j < i(会漏掉"整段从第 1 个开始"的情形,必须允许 j = 0);③ 忘记 dp[0] = 0;④ dp 初值设太小(应设成很大的数,如 4e18)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
4
1 2 -3 4
6题面样例 1:最优为 [1][2][−3 4]
6
-1 -1 4 -5 -1 4
0题面样例 2(总和为 0,整段不切即 0)
1
5
25只有一个数,只能作为一段
2
3 -3
0整段和为 0
3
0 0 0
0全为 0,怎么切都是 0
✅
自查清单:① 用 long long 吗?② j 从 0 开始吗?③ dp[0] = 0 吗?

🚨 易错点清单

⚠️
用 int:段和平方可达 4 × 10¹⁰,必须 long long。
⚠️
j 从 1 开始:必须允许 j = 0(整段作为最后一段)。
⚠️
贪心切分:有负数时贪心不保证最优。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
2000
运算量
约 2 × 10⁶

时间怎么算的?

空间都用在哪?

数组 a、前缀和 pre、dp 各 O(n)。

✅ 约 200 万次操作,瞬间完成。n ≤ 2000 的范围正是为 O(n²) 的划分 DP 设计的。

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

🔗 常用技巧小抄

// 分段型 DP 的通用骨架
dp[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)          // 枚举最后一段 [j+1, i]
        dp[i] = min(dp[i], dp[j] + cost(j + 1, i));
// 答案 = dp[n]

// 本题的 cost 就是段和的平方,借助前缀和 O(1) 求出

// 同类问题
// - 每段代价 = 段和(绝对值):贪心恰好可行
// - 每段代价 = 段和²:需要 DP(本题)
// - 每段代价 = 段长的平方:也需 DP
// - 每段代价 = (段和 - 目标)²:斜率优化 DP(进阶)

// 若 n 放大到 10^5,就需要"四边形不等式优化"或"斜率优化"
// 把 O(n^2) 降到 O(n log n) 或 O(n)
// 那是更高等级的内容,本题不需要

🌟 举一反三

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

能力点本题怎么用还能迁移到
分段型 DPdp[i] 枚举最后一段所有"切分序列"的最优化问题
前缀和O(1) 求段和区间求和的标准工具
平方代价对长段惩罚更重凸代价型问题(可用斜率优化)
🌟
思考题:如果题目改成"每段代价是段和的绝对值"(即 |段和|),最优解会变简单吗?(提示:会简单很多——因为绝对值满足三角不等式,把相邻两段合并不会让代价变大,所以"尽量少切"往往最优,可以贪心甚至直接判断。代价函数的性质(凸性、三角不等式)直接决定了能不能用贪心。)