link
剧透
方差计算式：\(n \sum a_i - (\sum a_i)^2\)
剧透
方差是 \(\min_d \{\sum_i (a_i-d)^2\}\)，可以随意选择 \(d\)
剧透
不妨多尝试几种转移顺序。
剧透
尝试加强你的性质，比如，证明差分序列严格单谷是最优的。
题意：给定数列 \(a\)，每次可以令 \(a_i \larr a_{i-1}+a_{i+1}-a_i\)，要求经过若干次操作后 \(a\) 数列方差的最小值。
观察性质
首先，这个操作是交换相邻两项的差分。
然后感性理解一下，为了让数靠近平均值，差分序列一定大致是单谷的。
严谨证明：
记序列 \(a\) 的平均值为 \(d\)，记 \(a_p \leq d \leq a_{p+1}\)。
对于所有 \(a_i(i > p)\)，如果差分不是单调的，我们可以邻项交换，使得 \(\sum_{i} (a'_i - d)^2 \leq \sum_{i} (a_i - d)^2\)，而前者大于等于新的方差。
对于 \(a_i(i \leq p)\) 同理。
对于恰好跨过 \(d\) 的那个差分（即 \(a_{p+1} - a_p\)），可以证明，这个差分可以与其中一边交换，使得新的方差变小。
因此差分序列是严格的单谷。
我们可以设计 \(dp\)，目前有两个方向：从中间往两边插入，或者从两边往中间插入。
从中间往两边
考虑最终的答案为 \(n \sum a_i^2 - (\sum a_i)^2\)，我们需要记录 \(\sum a_i\) 和 \(\sum a_i^2\)。
对差分序列 \(b\) 从小往大开始插入，每次插到头尾。
发现无论把 \(b_k\) 插入到开头和结尾，都可以根据已知的 \(x = \sum a_i\) 和 \(y = \sum a_i^2\) 推理出新的值。
因此我们可以直接设计 \(f_{i,s}\) 表示考虑到第 \(i\) 个差分，且 \(\sum a_i = s\) 时，\(\sum a_i^2\) 的最小值。
转移复杂度 \(O(1)\)，状态数是 \(O(n^2a)\)，总复杂度 \(O(n^2a)\)。
从两边往中间
这里使用 \(n \sum a_i^2 - (\sum a_i)^2\) 就不太好使了，因为还需要多记录下前面数的和，多了一个 \(a\)。（当然也可以优化成上面的做法）
考虑方差的式子：\(\min_d \{\sum_i (a_i-d)^2\}\)。
枚举这个 \(d\) 的位置，每次跑一遍 dp，可以做到 \(O(n^2a^2)\)。
考虑到既枚举 \(d\)、又记录下来前缀和很浪费，尝试把 \(d\) 记录进状态里。
由于我们只关心 \(a_i-d\)，也就是当前数和 \(d\) 的相对位置，可以直接记录当前剩余没有放数的区间，和 \(d\) 的相对位置。
同样可以做到 \(O(n^2a)\)。
小优化
\(O(n^2a)\) 不能通过本题，但是已经很接近了。考虑怎么乱搞一下。
发现差分数组非 \(0\) 的值只有 \(\min(n,a)\) 项，而 \(0\) 对转移没什么影响。
所以只需要对所有非 \(0\) 项做转移即可。
复杂度 \(O(\min(n,a)na)\)。