把数组划分成若干连续子段,使各段和的平方之和最小。
把数组 A 划分为若干非空连续子段。一个子段的偏差值是段内元素和的平方;整个划分的偏差值是各段偏差值之和。求最小的偏差值。
dp[i] = 前 i 个数划分后的最小偏差值。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 |
| 段的性质 | 非空、连续 |
dp[i]:前 i 个数的最小偏差值,dp[0] = 0[j+1, i]:dp[i] = min(dp[j] + (pre[i] − pre[j])²)= pre[i] − pre[j],O(1) 求出先算前缀和:0、1、3、0、4。
| 划分方案 | 各段和 | 偏差值 |
|---|---|---|
| [1 2 −3 4] | 4 | 16 |
| [1 2 −3][4] | 0, 4 | 0 + 16 = 16 |
| [1][2 −3 4] | 1, 3 | 1 + 9 = 10 |
| [1 2][−3 4] | 3, 1 | 9 + 1 = 10 |
| [1][2][−3 4] | 1, 2, 1 | 1 + 4 + 1 = 6 |
| [1][2][−3][4] | 1, 2, −3, 4 | 1 + 4 + 9 + 16 = 30 |
最小偏差值 6 ✓
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]。这组数据的总和恰好是 0,所以"整段不切"就能拿到 0 分。
(−1) + (−1) + 4 + (−5) + (−1) + 4
= −1 − 1 + 4 − 5 − 1 + 4
= 0
所以整段偏差 = 0² = 0
✅ 答案 0
dp[6] 会考虑 j = 0 的情况
即整段作为最后一段:dp[0] + (pre[6] − pre[0])² = 0
而偏差值不可能为负(平方和 ≥ 0)
所以 0 就是最小值
✅ 下界达到
因为偏差值是平方和,所以永远 ≥ 0。因此一旦能凑出"所有段和都为 0",就得到了理论最小值 0。
dp[i] 枚举最后一段起点 j,用前缀和 O(1) 取段和
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+2+(−3) = 0,合起来不花代价,但如果贪心一路拆开反而更贵(30 > 6)。| 方案 | 复杂度 | 正确性 |
|---|---|---|
| 划分 DP | O(n²) | ✅ 最优 |
| 贪心切分 | O(n) | ❌ 有反例 |
输入数组,程序会算出最小偏差值并给出最优划分方案。
点按钮开始 →
#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⁹)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 6 | 题面样例 1:最优为 [1][2][−3 4] |
6 | 0 | 题面样例 2(总和为 0,整段不切即 0) |
1 | 25 | 只有一个数,只能作为一段 |
2 | 0 | 整段和为 0 |
3 | 0 | 全为 0,怎么切都是 0 |
j = 0(整段作为最后一段)。数组 a、前缀和 pre、dp 各 O(n)。
✅ 约 200 万次操作,瞬间完成。n ≤ 2000 的范围正是为 O(n²) 的划分 DP 设计的。
// 分段型 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) // 那是更高等级的内容,本题不需要
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 分段型 DP | dp[i] 枚举最后一段 | 所有"切分序列"的最优化问题 |
| 前缀和 | O(1) 求段和 | 区间求和的标准工具 |
| 平方代价 | 对长段惩罚更重 | 凸代价型问题(可用斜率优化) |
|段和|),最优解会变简单吗?(提示:会简单很多——因为绝对值满足三角不等式,把相邻两段合并不会让代价变大,所以"尽量少切"往往最优,可以贪心甚至直接判断。代价函数的性质(凸性、三角不等式)直接决定了能不能用贪心。)