数组划分
EXY-PG-0245
题目描述
给定 $n$ 个整数构成的数组 $A=[a_{1},a_{2},…,a_{n}]$。
你需要将数组 $A$ 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。
形式化地，你可以将 $A$ 划分为若干非空连续子段 $A_{1},A_{2},…,A_{k}$，使得 $A=A_{1}+A_{2}+…+A_{k}$，这里的 $+$ 代表数组的连接。对于 $1≤i≤k$，设数组 $A_{i}=[a_{1}^{(i)},…,a_{m_i}^{(i)}]$ 包含 $m_{i}$ 个整数。你需要最小化 $\sum_{i=1}^k(\sum_{j=1}^{m_i}a_{j}^{(i)})^2$。
输入格式
第一行，一个正整数 $n$，表示数组 $A$ 的长度。
第二行，$n$ 个整数 $a_{1},a_{2},…,a_{n}$，表示数组 $A$。
输出格式
一行，一个整数，表示划分方案偏差值的最小值。
样例说明
样例 1
输入：
4
1 2 -3 4
输出：
6样例 2
输入：
6
-1 -1 4 -5 -1 4
输出：
0数据范围
对于 40% 的测试点，保证 $0≤a_{i}≤50$。
对于所有测试点，保证 $1≤n≤2000$，$−100≤a_{i}≤100$。