A106.方差

省选/NOI-

NOIP提高组

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定长度为 nn 的非严格递增正整数数列 1a1a2an1 \le a_1 \le a_2 \le \cdots \le a_n。每次可以进行的操作是:任意选择一个正整数 1<i<n1 < i < n,将 aia_i 变为 ai1+ai+1aia_{i - 1} + a_{i + 1} - a_i。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 n2n^2 的结果。

其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 D=1ni=1n(aiaˉ)2D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2,其中 aˉ=1ni=1nai\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i

输入格式

输入的第一行包含一个正整数 nn,保证 n104n \le {10}^4

输入的第二行有 nn 个正整数,其中第 ii 个数字表示 aia_i 的值。数据保证 1a1a2an1 \le a_1 \le a_2 \le \cdots \le a_n

输出格式

输出仅一行,包含一个非负整数,表示你所求的方差的最小值的 n2n^2 倍。

输入输出样例

  • 输入#1

    4
    1 2 4 6

    输出#1

    52

说明/提示

【样例解释 #1】

对于 (a1,a2,a3,a4)=(1,2,4,6)(a_1, a_2, a_3, a_4) = (1, 2, 4, 6),第一次操作得到的数列有 (1,3,4,6)(1, 3, 4, 6),第二次操作得到的新的数列有 (1,3,5,6)(1, 3, 5, 6)。之后无法得到新的数列。

对于 (a1,a2,a3,a4)=(1,2,4,6)(a_1, a_2, a_3, a_4) = (1, 2, 4, 6),平均值为 134\frac{13}{4},方差为 14((1134)2+(2134)2+(4134)2+(6134)2)=5916\frac{1}{4}({(1 - \frac{13}{4})}^2 + {(2 - \frac{13}{4})}^2 + {(4 - \frac{13}{4})}^2 + {(6 - \frac{13}{4})}^2) = \frac{59}{16}

对于 (a1,a2,a3,a4)=(1,3,4,6)(a_1, a_2, a_3, a_4) = (1, 3, 4, 6),平均值为 72\frac{7}{2},方差为 14((172)2+(372)2+(472)2+(672)2)=134\frac{1}{4} ({(1 - \frac{7}{2})}^2 + {(3 - \frac{7}{2})}^2 + {(4 - \frac{7}{2})}^2 + {(6 - \frac{7}{2})}^2) = \frac{13}{4}

对于 (a1,a2,a3,a4)=(1,3,5,6)(a_1, a_2, a_3, a_4) = (1, 3, 5, 6),平均值为 154\frac{15}{4},方差为 14((1154)2+(3154)2+(5154)2+(6154)2)=5916\frac{1}{4} ({(1 - \frac{15}{4})}^2 + {(3 - \frac{15}{4})}^2 + {(5 - \frac{15}{4})}^2 + {(6 - \frac{15}{4})}^2) = \frac{59}{16}

【数据范围】

测试点编号 nn \le aia_i \le
131 \sim 3 44 1010
454 \sim 5 1010 4040
686 \sim 8 1515 2020
9129 \sim 12 2020 300300
131513 \sim 15 5050 7070
161816 \sim 18 100100 4040
192219 \sim 22 400400 600600
232523 \sim 25 104{10}^4 5050

对于所有的数据,保证 1n1041 \le n \le {10}^41ai6001 \le a_i \le 600

首页