3921. T3-[NOIP2021] 方差(variance)
时间限制：1000 MS 内存限制：512 MB
题目描述
给定长度为 $ n $ 的非严格递增正整数数列$ 1≤a\_1≤a\_2≤⋯≤a\_n $。 每次可以进行的操作是：任意选择一个正整数 $ 1<i<n $ ，将 $ a\_i $ 变为 $ a\_{i−1}+a\_{i+1}−a\_i $ 。 求在若干次操作之后，该数列的方差最小值是多少。 请输出最小值乘以 $ n^2 $ 的结果。 其中方差的定义为：数列中每个数与平均值的差的平方的平均值。 更形式化地说，方差的定义为 $ D=\frac{1}{n}\textstyle\sum\_{i=1}^{n}(a\_i-\bar{a})^2 $ ，其中 $ \bar{a}=\frac{1}{n}\textstyle\sum\_{i=1}^{n}a\_i $ 。 #### 输入格式 输入的第一行包含一个正整数 $ n $ ，保证 $ n≤10^4 $。 输入的第二行有 $ n $ 个正整数，其中第 $ i $ 个数字表示 $ a\_i $的值。数据保证 $ 1≤a\_1≤a\_2≤⋅⋅⋅≤a\_n $。 #### 输出格式 输出仅一行，包含一个非负整数，表示你所求的方差的最小值的 $ n^2 $倍。 #### 数据范围  对于所有的数据，保证 $ n≤10000 $ ，$ a\_i≤600 $ #### 输入样例： ``` 4 1 2 4 6 ``` #### 输出样例： ``` 52 ``` #### 样例解释 对于 $ (a\_1,a\_2,a\_3,a\_4)=(1,2,4,6) $ ,第一次操作得到的数列有 $ (1,3,4,6) $ 第二次操作得到的新的数列有 $ (1,3,5,6) $ 。之后无法得到新的数列。 对于$ (a\_1,a\_2,a\_3,a\_4)=(1,2,4,6) $ ,平均值为 $ \frac{13}{4} $ 方差为 $ \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} $ 。 对于 $ (a\_1,a\_2,a\_3,a\_4)=(1,3,4,6) $, 平均值为 $ \frac{7}{2} $ ，方差为 $ \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} $ 。 对于 $ (a\_1,a\_2,a\_3,a\_4)=(1,3,5,6) $, 平均值为 $ \frac{15}{4} $ ，方差为 $ \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} $ 。