[GESP202609 六级] 数组划分
题目描述
nnn 个整数的数组 A=[a1,a2,…,an]A = [a_1, a_2, \dots, a_n]A=[a1 ,a2 ,…,an ]。
将 AAA 划分成若干个非空连续子段，某个子段的偏差值定义为子段内整数和的平方。任意一个划分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。形式化的，你可以将 A 划分成若干非空连续子段 A1,A2,…,AkA_1, A_2, \dots, A_kA1 ,A2 ,…,Ak ，使得 A=A1+A2+⋯+AkA = A_1 + A_2 + \dots + A_kA=A1 +A2 +⋯+Ak ，这里的 + 代表数组的连接。对于非负 k，设数组 Ai=[a1(i),…,ami(i)]A_i = [a_{1}^{(i)}, \dots, a_{m_i}^{(i)}]Ai =[a1(i) ,…,ami (i) ] 包含 m 个整数，你需要最小化
∑i=1k(∑j=1miaj(i))2\sum_{i=1}^{k} \left ( \sum_{j=1}^{m_i} a_{j}^{(i)} \right)^2∑i=1k (∑j=1mi aj(i) )2
输入格式
共两行。第一行包含一个整数 nnn，表示数组 AAA 的长度。
第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,\dots,a_na1 ,a2 ,…,an ，相邻两个整数之间用一个空格分隔。
输出格式
一行包含一个整数，表示所有划分方案中最小的偏差值。
输入输出样例
输入#1
输出#1
输入#2
输出#2
数据范围：
对于40%的数据，0≤n,ai≤500 \leq n, a_i \leq 500≤n,ai ≤50
对于100%的数据，1≤n≤2000，−100≤ai≤1001 \leq n \leq 2000，-100 \leq a_i \leq 1001≤n≤2000，−100≤ai ≤100
