P7962 [NOIP2021] 方差 题解

考虑沿用 CBC022E 的套路，把题面中给的操作扔到 $a$ 的差分数组里，容易发现其实就是交换两个相邻的数的差分值。

套路的把方差乘以 $n^2$ 拆成 $n\sum\limits_{i=1}^na_i^2-(\sum\limits_{i=1}^na_i)^2$ 的形式，然后考虑 dp 处理。设 $f_{i,j}$ 表示当前处理完了前 $i-1$ 个差分值，此时平方项的和值为 $j$，最少花费是多少。把方差的形式用差分的前缀和的形式展开然后合并同类项，可以发现最后得到的式子是一个单峰的形式，因此对于前面给出的 dp，插入一个新的元素要么插入到其最左侧要么插入到其最右侧。转移是容易的。

直接这样做时间复杂度为 $O(n^2a)$，难以通过。考虑继续优化。注意到 dp 上值不为 $0$ 的数是很少的，所以考虑只转移 dp 不为 $0$ 的情况，容易计算得出这样的位置的数量是只有 $O(a)$ 个的。因此此时总时间复杂度为 $O(na^2)$，可以通过该题。