说一下这个题的卡时做法

在你得出差分序列单谷的性质之后，有这样一个dp：

强行钦定差分序列最小值处的 $a=0$ ，然后变成从小到大枚举差分值，往左或往右放的问题。

设 $f[l][r][s]$ 表示往左放的差分值和是 $l$ ，往右放的差分值和是 $r$ ，目前已有的 $a_i$ 和为 $s$ 的情况下，$\sum a_i^2$ 最小是多少。

理论上这个 $s$ 最大可能到 $O(nm)$ ( $m$ 是 $a_i$ 的最大值)，但这题的评论区里已经有人说了这一维不太可能跑满，所以你大概卡一个上界（比如常数倍的 $m$ ）就行了。

但如果你不知道这个上界到底开多少才稳妥，还有这么一个卡时做法：

枚举最终所有数的和 $s$ ，然后在dp时直接省略 $s$ 这一维， $dp[l][r]$ 表示左边差分值的和 $l$ 右边差分值的和 $r$ 的情况下， $\sum (na_i - s)^2$ 最小是多少。

注意看上去这个式子因为没有在dp里控制真正的 $\sum a_i$ 是多少，但是结果却是对的，因为如果你把方差的计算公式 $\sum(a_i-\overline{a})^2/n$ 中的 $\overline{a}$ 换成别的值的话只会让算出来的方差偏大，所有的东西求个最小值之后就只剩下最优解里正确的 $s$ 算出来的方差了。

这样一来你就可以枚举 $s$ 然后卡时，单次dp是 $O(m^2)$ 的。

目前我们没有任何人能卡掉这个做法（盲猜CCF也卡不掉），所以我们猜最终答案中这个 $s$ 可能就是最多 $O(m)$ 级别的，但我们也不会证明。

所以有谁能证明这个结论或构造能卡掉这个卡时做法的数据吗qwq