大致思路是这样的：根据差分数组的单谷性从小到大考虑所有差分值 $d_i$。由于不关心 $a_i$ 具体值而是它们的相对大小，因此固定原数组中某个位置 $a_p=0$，并向其左 / 右添加差分值。

设 $f_{i,j,k}$ 表示考虑到前 $i$ 个差分值，放在 $p$ 左边的差分值之和为 $j$ 且所有 $a$ 的和为 $k$（因为最终柿子是 $n(\sum a_i^2)-(\sum a_i)^2$ 所以要记录 $\sum a_i$）时 $\sum a_i^2$ 的最小值。转移就枚举当前 $d_i$ 放左边（那么新的 $a_x$ 就是 $-j-d_i$）或右边（新的 $a_x$ 是 $(\sum_{x=1}^{i-1}d_i)-j+d_i$）。

那么问题来了。很显然，为了确保正确性 $k$ 这一维应该开到可能的 $\sum a_i$ 的最大值，是 $\mathcal{O}(\min(n,V)\times V)$ 级别的（为 $0$ 的差分值对答案无影响），但实际上由于正负抵消，整个过程中任何时刻 $|\sum a_i|$ 的最大值不会太大（但仍有可能是 $V^2$ 级别）。根据这一感性的猜测我在考场上把 $k$ 这一维大小设成了 $12V$（为了平衡正确性和用时），但是在洛谷上测将其设为 $V$ 都能通过（见 评测记录），故猜测任何时候 $|\sum a_i|$ 的最大值是线性而非平方的，且有上界 $V\sim 2V$，求证明或给出 hack 数据。/kel