7475. [GESP202609 六级] 数组划分
时间限制：1000 MS 内存限制：256 MB
题目描述
#### 题目描述 给定 $n$ 个整数构成的数组 $A=[a\_1,a\_2,\ldots,a\_n]$。 你需要将数组 $A$ 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。 你需要最小化划分方案的偏差值。 形式化地，你可以将 $A$ 划分为若干非空连续子段 $A\_1,A\_2,\ldots,A\_k$，使得 $A=A\_1+A\_2+\ldots+A\_k$，这里的 $+$ 代表数组的连接。对于 $1\le i\le k$，设数组 $A\_i=[a\_1^{(i)},\ldots,a\_{m\_i}^{(i)}]$ 包含 $m\_i$ 个整数。你需要最小化 $\sum\_{i=1}^{k}\left(\sum\_{j=1}^{m\_i}a\_j^{(i)}\right)^2$。 #### 输入格式 第一行，一个正整数 $n$，表示数组 $A$ 的长度。 第二行，$n$ 个整数 $a\_1,a\_2,\ldots,a\_n$，表示数组 $A$。 #### 输出格式 一行，一个整数，表示划分方案偏差值的最小值。 #### 输入输出样例 #1 ##### 输入 #1 ``` 4 1 2 -3 4 ``` ##### 输出 #1 ``` 6 ``` #### 输入输出样例 #2 ##### 输入 #2 ``` 6 -1 -1 4 -5 -1 4 ``` ##### 输出 #2 ``` 0 ``` #### 说明/提示 对于 $40\%$ 的测试点，保证 $0\le a\_i\le 50$。 对于所有测试点，保证 $1\le n\le 2000$，$-100\le a\_i\le 100$。