#G1196. [GESP202609 六级] 数组划分

[GESP202609 六级] 数组划分

[GESP202609 六级] 数组划分

时间限制:1.0 s  内存限制:512.0 MB

题目描述

给定 nn 个整数构成的数组 AA。

你需要将数组 AA 划分为若干非空连续子段。对于划分得到的某个子段,它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。

你需要最小化划分方案的偏差值。

形式化地,你可以将 AA 划分为若干非空连续子段 A1,A2,…,AkA_1, A_2, \dots, A_k,使得 A=A1+A2+⋯+AkA = A_1 + A_2 + \dots + A_k,这里的 ++ 代表数组的连接。对于 1≤i≤k1 \le i \le k,设数组 Ai=[a1(i),…,ami(i)]A_i = [a_1^{(i)}, \dots, a_{m_i}^{(i)}] 包含 mim_i 个整数。你需要最小化 $\displaystyle\sum_{i=1}^{k} \left( \sum_{j=1}^{m_i} a_j^{(i)} \right)^2$。

输入格式

第一行,一个正整数 nn,表示数组 AA 的长度。

第二行,nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示数组 AA。

输出格式

一行,一个整数,表示划分方案偏差值的最小值。

样例 #1

样例输入 #1

4
1 2 -3 4

样例输出 #1

6

样例 #2

样例输入 #2

6
-1 -1 4 -5 -1 4

样例输出 #2

0

数据范围

测试点 数据范围 说明
1~4 0≤ai≤500 \le a_i \le 50 无
全部 1≤n≤20001 \le n \le 2000,−100≤ai≤100-100 \le a_i \le 100